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