Artifact c6d3325f9b7a789bbab3583d479611ec8e40be05
//-------------------------------------------------------------
// Dinic's Algorithm
// O(V E)
//
// G : bidirectional (G[i].has(j) <==> G[j].has(i))
// F : flow-capacity F[i][j] = Capacity, F[j][i] = 0
//
// Verified by
// - SRM 399 Div1 LV3
// - PKU 1459
// - CodeCraft 09 CUTS
// - SRM 465 Div1 LV2
//-------------------------------------------------------------
static const int NV = 512;
typedef int flow;
typedef int vert;
typedef vert edge;
typedef vector<edge> edges;
typedef vector<edges> graph;
typedef flow flow_graph[NV][NV];
flow dinic_dfs( graph& G, flow_graph F, vert v, vert D,
int LV[], flow flow_in, int blocked[] )
{
flow flow_out = 0;
for(int i=0; i!=G[v].size(); ++i) {
int u = G[v][i];
if( LV[v]+1==LV[u] && F[v][u] ) {
flow f = min(flow_in-flow_out, F[v][u]);
if( u==D || !blocked[u] && (f=dinic_dfs(G,F,u,D,LV,f,blocked)) ) {
F[v][u] -= f;
F[u][v] += f;
flow_out += f;
if( flow_in == flow_out ) return flow_out;
}
}
}
blocked[v] = (flow_out==0);
return flow_out;
}
flow maxFlow( graph& G, flow_graph F, vert S, vert D )
{
for( flow total=0 ;; ) {
int LV[NV] = {0};
vector<int> Q(1, S);
for(int lv=1; !Q.empty(); ++lv) {
vector<int> Q2;
for(int i=0; i!=Q.size(); ++i) {
edges& ne = G[Q[i]];
for(int j=0; j!=ne.size(); ++j)
if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
LV[ne[j]]=lv, Q2.push_back(ne[j]);
}
Q.swap(Q2);
}
if( !LV[D] )
return total;
int blocked[NV] = {};
total += dinic_dfs( G, F, S, D, LV, 0x7fffffff, blocked );
}
}