4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: // MinCost-MaxFlow
4fd800b3a8 2011-02-23        kinaba: //   O(??)
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: // Verified by
4fd800b3a8 2011-02-23        kinaba: //   - SRM 487 Div2 LV3
4fd800b3a8 2011-02-23        kinaba: //   - SRM 491 Div1 LV3
4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <map>
4fd800b3a8 2011-02-23        kinaba: #include <queue>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<typename T>
4fd800b3a8 2011-02-23        kinaba: class IdGen
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	map<T, int> v2id_;
4fd800b3a8 2011-02-23        kinaba: 	vector<T>   id2v_;
4fd800b3a8 2011-02-23        kinaba: public:
4fd800b3a8 2011-02-23        kinaba: 	int v2id(const T& v) {
4fd800b3a8 2011-02-23        kinaba: 		if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
4fd800b3a8 2011-02-23        kinaba: 		return v2id_[v];
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	const T& id2v(int i) const { return id2v_[i]; }
4fd800b3a8 2011-02-23        kinaba: 	int size() const { return id2v_.size(); }
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<typename Vert, typename Cost, typename Flow, int NV=256>
4fd800b3a8 2011-02-23        kinaba: class MinCostFlow
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	IdGen<Vert> idgen;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	vector<int> G[NV];
4fd800b3a8 2011-02-23        kinaba: 	Flow F[NV][NV];
4fd800b3a8 2011-02-23        kinaba: 	Cost C[NV][NV];
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: public:
4fd800b3a8 2011-02-23        kinaba: 	void addEdge( Vert s_, Vert t_, Cost c, Flow f )
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int s = idgen.v2id(s_), t = idgen.v2id(t_);
4fd800b3a8 2011-02-23        kinaba: 		G[s].push_back(t);
4fd800b3a8 2011-02-23        kinaba: 		G[t].push_back(s);
4fd800b3a8 2011-02-23        kinaba: 		C[s][t] = c;
4fd800b3a8 2011-02-23        kinaba: 		C[t][s] = -c;
4fd800b3a8 2011-02-23        kinaba: 		F[s][t] = f;
4fd800b3a8 2011-02-23        kinaba: 		F[t][s] = 0;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	pair<Cost, Flow> calc( Vert s_, Vert t_ )
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_);
4fd800b3a8 2011-02-23        kinaba: 		static const Cost COST_INF = 1e+300; // !!EDIT HERE!!
4fd800b3a8 2011-02-23        kinaba: 		static const Flow FLOW_INF = 0x7fffffff;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		Cost total_cost = 0;
4fd800b3a8 2011-02-23        kinaba: 		Flow total_flow = 0;
4fd800b3a8 2011-02-23        kinaba: 		vector<Cost> h(N, 0); // potential
4fd800b3a8 2011-02-23        kinaba: 		for(Flow RF=FLOW_INF; RF>0; ) // residual flow
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			// Dijkstra -- find the min-cost path
4fd800b3a8 2011-02-23        kinaba: 			vector<Cost> d(N, COST_INF);  d[S] = 0;
4fd800b3a8 2011-02-23        kinaba: 			vector<int>  prev(N, -1);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			typedef pair< Cost, pair<int,int> > cedge;
4fd800b3a8 2011-02-23        kinaba: 			priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
4fd800b3a8 2011-02-23        kinaba: 			Q.push( cedge(0, make_pair(S,S)) );
4fd800b3a8 2011-02-23        kinaba: 			while( !Q.empty() ) {
4fd800b3a8 2011-02-23        kinaba: 				cedge e = Q.top(); Q.pop();
4fd800b3a8 2011-02-23        kinaba: 				if( prev[e.second.second] >= 0 )
4fd800b3a8 2011-02-23        kinaba: 					continue;
4fd800b3a8 2011-02-23        kinaba: 				prev[e.second.second] = e.second.first;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 				int u = e.second.second;
4fd800b3a8 2011-02-23        kinaba: 				for(int i=0; i<G[u].size(); ++i) {
4fd800b3a8 2011-02-23        kinaba: 					int  v = G[u][i];
4fd800b3a8 2011-02-23        kinaba: 					Cost r_cost = C[u][v] + h[u] - h[v];
4fd800b3a8 2011-02-23        kinaba: 					if( F[u][v] > 0 && d[v] > d[u]+r_cost )
4fd800b3a8 2011-02-23        kinaba: 						Q.push( cedge(d[v]=d[u]+r_cost, make_pair(u,v)) );
4fd800b3a8 2011-02-23        kinaba: 				}
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			if( prev[T] < 0 )
4fd800b3a8 2011-02-23        kinaba: 				break; // Finished
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			// Run the flow as much as possible
4fd800b3a8 2011-02-23        kinaba: 			Flow f = RF;
4fd800b3a8 2011-02-23        kinaba: 			for(int u=T; u!=S; u=prev[u])
4fd800b3a8 2011-02-23        kinaba: 				f = min(f, F[prev[u]][u]);
4fd800b3a8 2011-02-23        kinaba: 			RF         -= f;
4fd800b3a8 2011-02-23        kinaba: 			total_flow += f;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			for(int u=T; u!=S; u=prev[u])
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				total_cost    += f * C[prev[u]][u];
4fd800b3a8 2011-02-23        kinaba: 				F[prev[u]][u] -= f;
4fd800b3a8 2011-02-23        kinaba: 				F[u][prev[u]] += f;
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			// Update the potential
4fd800b3a8 2011-02-23        kinaba: 			for(int u=0; u<N; ++u)
4fd800b3a8 2011-02-23        kinaba: 				h[u] += d[u];
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return make_pair(total_cost, total_flow);
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };