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: 
11265aa172 2011-09-18        kinaba: template<typename T>
11265aa172 2011-09-18        kinaba: class IdGen
23dfcca431 2011-02-23        kinaba: {
11265aa172 2011-09-18        kinaba: 	map<T, int> v2id_;
11265aa172 2011-09-18        kinaba: 	vector<T>   id2v_;
11265aa172 2011-09-18        kinaba: public:
11265aa172 2011-09-18        kinaba: 	int v2id(const T& v) {
11265aa172 2011-09-18        kinaba: 		if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
11265aa172 2011-09-18        kinaba: 		return v2id_[v];
23dfcca431 2011-02-23        kinaba: 	}
11265aa172 2011-09-18        kinaba: 	const T& id2v(int i) const { return id2v_[i]; }
11265aa172 2011-09-18        kinaba: 	int size() const { return id2v_.size(); }
11265aa172 2011-09-18        kinaba: };
23dfcca431 2011-02-23        kinaba: 
11265aa172 2011-09-18        kinaba: template<typename Vert, typename Flow, int NV=512>
11265aa172 2011-09-18        kinaba: class MaxFlow
23dfcca431 2011-02-23        kinaba: {
11265aa172 2011-09-18        kinaba: 	IdGen<Vert> idgen;
11265aa172 2011-09-18        kinaba: 	vector<int> G[NV];
11265aa172 2011-09-18        kinaba: 	Flow F[NV][NV];
11265aa172 2011-09-18        kinaba: 
11265aa172 2011-09-18        kinaba: public:
11265aa172 2011-09-18        kinaba: 	void addEdge( Vert s_, Vert t_, Flow f )
11265aa172 2011-09-18        kinaba: 	{
11265aa172 2011-09-18        kinaba: 		const int s = idgen.v2id(s_), t = idgen.v2id(t_);
11265aa172 2011-09-18        kinaba: 		G[s].push_back(t);
11265aa172 2011-09-18        kinaba: 		G[t].push_back(s);
11265aa172 2011-09-18        kinaba: 		F[s][t] = f;
11265aa172 2011-09-18        kinaba: 		F[t][s] = 0;
11265aa172 2011-09-18        kinaba: 	}
11265aa172 2011-09-18        kinaba: 
11265aa172 2011-09-18        kinaba: 	Flow calc( Vert s_, Vert t_ )
11265aa172 2011-09-18        kinaba: 	{
11265aa172 2011-09-18        kinaba: 		const int S = idgen.v2id(s_), D = idgen.v2id(t_);
11265aa172 2011-09-18        kinaba: 		for( Flow total=0 ;; ) {
11265aa172 2011-09-18        kinaba: 			// Do BFS and compute the level for each node.
11265aa172 2011-09-18        kinaba: 			int LV[NV] = {0};
11265aa172 2011-09-18        kinaba: 			vector<int> Q(1, S);
11265aa172 2011-09-18        kinaba: 			for(int lv=1; !Q.empty(); ++lv) {
11265aa172 2011-09-18        kinaba: 				vector<int> Q2;
11265aa172 2011-09-18        kinaba: 				for(size_t i=0; i!=Q.size(); ++i) {
11265aa172 2011-09-18        kinaba: 					const vector<int>& ne = G[Q[i]];
11265aa172 2011-09-18        kinaba: 					for(size_t j=0; j!=ne.size(); ++j)
11265aa172 2011-09-18        kinaba: 						if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
11265aa172 2011-09-18        kinaba: 							LV[ne[j]]=lv, Q2.push_back(ne[j]);
11265aa172 2011-09-18        kinaba: 				}
11265aa172 2011-09-18        kinaba: 				Q.swap(Q2);
23dfcca431 2011-02-23        kinaba: 			}
11265aa172 2011-09-18        kinaba: 
11265aa172 2011-09-18        kinaba: 			// Destination is now unreachable. Done.
11265aa172 2011-09-18        kinaba: 			if( !LV[D] )
11265aa172 2011-09-18        kinaba: 				return total;
23dfcca431 2011-02-23        kinaba: 
11265aa172 2011-09-18        kinaba: 			// Iterating DFS.
11265aa172 2011-09-18        kinaba: 			bool blocked[NV] = {};
11265aa172 2011-09-18        kinaba: 			total += dinic_dfs( S, D, LV, 0x7fffffff, blocked );
11265aa172 2011-09-18        kinaba: 		}
11265aa172 2011-09-18        kinaba: 	}
23dfcca431 2011-02-23        kinaba: 
11265aa172 2011-09-18        kinaba: private:
11265aa172 2011-09-18        kinaba: 	Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] )
11265aa172 2011-09-18        kinaba: 	{
11265aa172 2011-09-18        kinaba: 		Flow flow_out = 0;
11265aa172 2011-09-18        kinaba: 		for(size_t i=0; i!=G[v].size(); ++i) {
11265aa172 2011-09-18        kinaba: 			int u = G[v][i];
11265aa172 2011-09-18        kinaba: 			if( LV[v]+1==LV[u] && F[v][u] ) {
11265aa172 2011-09-18        kinaba: 				Flow f = min(flow_in-flow_out, F[v][u]);
11265aa172 2011-09-18        kinaba: 				if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) {
11265aa172 2011-09-18        kinaba: 					F[v][u]  -= f;
11265aa172 2011-09-18        kinaba: 					F[u][v]  += f;
11265aa172 2011-09-18        kinaba: 					flow_out += f;
11265aa172 2011-09-18        kinaba: 					if( flow_in == flow_out ) return flow_out;
11265aa172 2011-09-18        kinaba: 				}
11265aa172 2011-09-18        kinaba: 			}
11265aa172 2011-09-18        kinaba: 		}
11265aa172 2011-09-18        kinaba: 		blocked[v] = (flow_out==0);
11265aa172 2011-09-18        kinaba: 		return flow_out;
23dfcca431 2011-02-23        kinaba: 	}
11265aa172 2011-09-18        kinaba: };