Artifact Content
Not logged in

Artifact f71eec6e87c84091a249f6be60467b84f910c81b



//-------------------------------------------------------------
// 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
//
// Old versoin Verified by
//   - SRM 399 Div1 LV3
//   - PKU 1459
//   - CodeCraft 09 CUTS
//   - SRM 465 Div1 LV2
//   - SRM 543 Div1 LV3
//-------------------------------------------------------------

template<typename T>
class IdGen
{
	map<T, int> v2id_;
	vector<T>   id2v_;
public:
	int v2id(const T& v) {
		if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
		return v2id_[v];
	}
	const T& id2v(int i) const { return id2v_[i]; }
	int size() const { return id2v_.size(); }
};

template<typename Vert, typename Flow, int NV=50*50*8+2>
class MaxFlow
{
	typedef int Edge;

	vector<int>  G[NV];
	vector<Flow> F;

	IdGen<Vert> idgen;
	map<pair<int,int>, Edge> edge_id;
	vector<int>  Edge_to;
	vector<Edge> Edge_rev;

public:
	void add( Vert s_, Vert t_, Flow f )
	{
		const int s = idgen.v2id(s_), t = idgen.v2id(t_);
		if(!edge_id.count(make_pair(s,t))) {
			const int e = int(edge_id.size());
			edge_id[make_pair(s,t)] = e;
			edge_id[make_pair(t,s)] = e+1;
			G[s].push_back(e);
			G[t].push_back(e+1);
			F.push_back(0);
			F.push_back(0);
			Edge_rev.push_back(e+1);
			Edge_rev.push_back(e);
			Edge_to.push_back(t);
			Edge_to.push_back(s);
		}
		const Edge e = edge_id[make_pair(s,t)];
		F[e] = min(F[e]+f, INF);
	}

	Flow calc( Vert s_, Vert t_ )
	{
		const int S = idgen.v2id(s_), D = idgen.v2id(t_);
		for( Flow total=0 ;; ) {
			// Do BFS and compute the level for each node.
			int LV[NV] = {0};
			vector<int> Q(1, S);
			for(int lv=1; !Q.empty(); ++lv) {
				vector<int> Q2;
				for(size_t i=0; i!=Q.size(); ++i) {
					const vector<Edge>& ne = G[Q[i]];
					for(size_t j=0; j!=ne.size(); ++j) {
						Edge e = ne[j];
						int  t = Edge_to[e];
						if( F[e] && !LV[t] && t!=S )
							LV[t]=lv, Q2.push_back(t);
					}
				}
				Q.swap(Q2);
			}

			// Destination is now unreachable. Done.
			if( !LV[D] )
				return total;

			// Iterating DFS.
			bool blocked[NV] = {};
			total += dinic_dfs( S, D, LV, INF, blocked );
		}
	}

private:
	Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] )
	{
		Flow flow_out = 0;
		for(size_t i=0; i!=G[v].size(); ++i) {
			Edge e = G[v][i];
			int  u = Edge_to[e];
			if( LV[v]+1==LV[u] && F[e] ) {
				Flow f = min(flow_in-flow_out, F[e]);
				if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) {
					F[e]           -= f;
					F[Edge_rev[e]] += f;
					flow_out += f;
					if( flow_in == flow_out ) return flow_out;
				}
			}
		}
		blocked[v] = (flow_out==0);
		return flow_out;
	}
};