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

#include
#include
#include
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 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 ;
}