Template Dinic
Given N nodes, M arcs, returns max flow from 0 to N.
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair< int, int > pii; typedef pair< int, ll > pil; typedef pair< ll, int > pli; typedef pair< ll, ll > pll; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< ll > vl; typedef vector< vl > vvl; typedef vector< double > vd; typedef vector< vd > vvd; typedef vector< pii > vp; typedef vector< vp > vvp; typedef vector< bool > vb; typedef vector< vb > vvb; template< class T1, class T2 > bool upmin( T1 &x, T2 v ){ if( x > v ){ x = v; return true; } return false; } template< class T1, class T2 > bool upmax( T1 &x, T2 v ){ if( x < v ){ x = v; return true; } return false; } const int INF = 0x3f3f3f3f; struct Nedge{ // network edge int from, to, cap, flow; Nedge(){} Nedge( int _f, int _t, int _c, int _fl ){ from = _f; to = _t; cap = _c; flow = _fl; } }; struct Dinic{ int n, m, s, t; vector< Nedge > edge; vvi G; vb vis; vi dis; vi cur; Dinic( int sz ){ n = sz; edge.clear(); G.clear(); G.resize( sz ); vis.clear(); vis.resize( sz ); dis.clear(); dis.resize( sz ); cur.clear(); cur.resize( sz ); } void add_edge( int from, int to, int cap ){ edge.push_back( Nedge( from, to, cap, 0 ) ); edge.push_back( Nedge( to, from, 0, 0 ) ); m = edge.size(); G[ from ].push_back( m - 2 ); G[ to ].push_back( m - 1 ); } bool BFS(){ fill( vis.begin(), vis.end(), 0 ); queue< int > que; que.push( s ); dis[ s ] = 0; vis[ s ] = 1; while( not que.empty() ){ int x = que.front(); que.pop(); for( int i = 0; i < G[ x ].size(); ++i ){ Nedge &e = edge[ G[ x ][ i ] ]; if( not vis[ e.to ] and e.cap > e.flow ) vis[ e.to ] = 1, dis[ e.to ] = dis[ x ] + 1, que.push( e.to ); } } return vis[ t ]; } int DFS( int x, int a ){ if( x == t or a == 0 ) return a; int flow = 0, f; for( int &i = cur[ x ]; i < G[ x ].size(); ++i ){ // so that cycles won't matter, know what I mean? Nedge &e = edge[ G[ x ][ i ] ]; if( dis[ x ] + 1 == dis[ e.to ] and ( f = DFS( e.to, min( a, e.cap - e.flow ) ) ) > 0 ){ e.flow += f; edge[ G[ x ][ i ] ^ 1 ].flow -= f; flow += f; a -= f; if( a == 0 ) break; } } return flow; } int max_flow( int s, int t ){ this->s = s; this->t = t; int flow = 0; while( BFS() ) fill( cur.begin(), cur.end(), 0 ), flow += DFS( s, INF ); return flow; } }; void solve(){ int N, M; cin >> N >> M; Dinic *din = new Dinic( N ); for( int i = 0; i < M; ++i ){ int u, v, c; cin >> u >> v >> c; din->add_edge( u - 1, v - 1, c ); } cout << din->max_flow( 0, N - 1 ) << "\n"; } int main(){ ios::sync_with_stdio( false ); solve(); return 0; }