P3376 【模板】网络最大流(EK)

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const long long N = 5e3 + 1 ;
long long h [ N ] , to [ N << 1 ] , nt [ N << 1 ] , from [ N << 1 ];
long long w [ N << 1 ];
long long cnt , s , t , n , m ;
void add ( long long x , long long y , long long z ) {
    nt [ ++ cnt ] = h [ x ] ;
    h [ x ] = cnt ;
    from [ cnt ] = x;
    to [ cnt ] = y ;
    w [ cnt ] = z ;
}
long long ans = 0 ;
long long pre [ N << 1 ] ;
long long vis [ N << 1 ] , dist [ N << 1 ] ;
bool bfs ( ) {
    memset ( vis , 0 , sizeof vis );
    dist [ s ] = ( 1 << 30 ) ;
    vis [ s ] = 1 ;
    deque < long long > dq;
    dq . push_back ( s ) ;
    while ( ! dq . empty () ) {
        long long x = dq . front ( );
        dq . pop_front ( ) ;
        for ( long long i = h [ x ] ; i ; i = nt [ i ] ) {
            long long y = to [ i ] ;
            if ( vis [ y ] || w [ i ] == 0 ) continue;
            dist [ y ] = min ( dist [ x ] , w [ i ] ) ;
            pre [ y ] = i ;
            dq . push_back ( y ) ;
            vis [ y ] = 1 ;
            if ( y == t )
                return true;
        }
    }
    return false;
}
void update ( ) {
    long long now = t ;
    while ( now != s ) {
        static long long x ;
        x = pre [ now ] ;
        w [ x ] -= dist [ t ] ;
        w [ x ^ 1 ] += dist [ t ] ;
        now = from [ x ] ;
    }
    ans += dist [ t ] ;
}
int main ( ) {
    // freopen ( "text.in" , "r" , stdin ) ;
    cin >> n >> m >> s >> t ;
    cnt = 1 ;
    for ( long long i = 1 ; i <= m ; i ++ ){
        static long long x , y , z ;
        cin >> x >> y >> z ;
        add ( x , y , z ) ;
        add ( y , x , 0 ) ;
    }
    while ( bfs ( ) ) {
        update ( ) ;
    }
    printf ( "%lld\n" , ans ) ;
    return 0 ;
}