23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: // MinCost-MaxFlow
524cc07867 2012-04-03        kinaba: //   O(F E log E)    // F:flow
524cc07867 2012-04-03        kinaba: //   See http://d.hatena.ne.jp/tsukuno/20120320#1332179143
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // Verified by
524cc07867 2012-04-03        kinaba: //   - (SRM 487 Div2 LV3) in previous version
524cc07867 2012-04-03        kinaba: //   - (SRM 526 Div1 LV1) in previous version
23dfcca431 2011-02-23        kinaba: //   - SRM 491 Div1 LV3
23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: #include <iostream>
23dfcca431 2011-02-23        kinaba: #include <string>
23dfcca431 2011-02-23        kinaba: #include <vector>
23dfcca431 2011-02-23        kinaba: #include <map>
23dfcca431 2011-02-23        kinaba: #include <queue>
23dfcca431 2011-02-23        kinaba: using namespace std;
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: template<typename T>
23dfcca431 2011-02-23        kinaba: class IdGen
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	map<T, int> v2id_;
23dfcca431 2011-02-23        kinaba: 	vector<T>   id2v_;
23dfcca431 2011-02-23        kinaba: public:
23dfcca431 2011-02-23        kinaba: 	int v2id(const T& v) {
23dfcca431 2011-02-23        kinaba: 		if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
23dfcca431 2011-02-23        kinaba: 		return v2id_[v];
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: 	const T& id2v(int i) const { return id2v_[i]; }
23dfcca431 2011-02-23        kinaba: 	int size() const { return id2v_.size(); }
23dfcca431 2011-02-23        kinaba: };
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: template<typename Vert, typename Cost, typename Flow, int NV=256>
23dfcca431 2011-02-23        kinaba: class MinCostFlow
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	IdGen<Vert> idgen;
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	vector<int> G[NV];
23dfcca431 2011-02-23        kinaba: 	Flow F[NV][NV];
23dfcca431 2011-02-23        kinaba: 	Cost C[NV][NV];
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: public:
23dfcca431 2011-02-23        kinaba: 	void addEdge( Vert s_, Vert t_, Cost c, Flow f )
23dfcca431 2011-02-23        kinaba: 	{
23dfcca431 2011-02-23        kinaba: 		int s = idgen.v2id(s_), t = idgen.v2id(t_);
23dfcca431 2011-02-23        kinaba: 		G[s].push_back(t);
23dfcca431 2011-02-23        kinaba: 		G[t].push_back(s);
23dfcca431 2011-02-23        kinaba: 		C[s][t] = c;
23dfcca431 2011-02-23        kinaba: 		C[t][s] = -c;
23dfcca431 2011-02-23        kinaba: 		F[s][t] = f;
23dfcca431 2011-02-23        kinaba: 		F[t][s] = 0;
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	pair<Cost, Flow> calc( Vert s_, Vert t_ )
23dfcca431 2011-02-23        kinaba: 	{
23dfcca431 2011-02-23        kinaba: 		const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_);
524cc07867 2012-04-03        kinaba: 		static const Cost COST_INF = 1e+300; // !!EDIT HERE!!
524cc07867 2012-04-03        kinaba: 		static const Flow FLOW_INF = 0x7fffffff;
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 		Cost total_cost = 0;
23dfcca431 2011-02-23        kinaba: 		Flow total_flow = 0;
524cc07867 2012-04-03        kinaba: 		vector<Cost> dist(N, 0); // Distance from S : initially unknown.
524cc07867 2012-04-03        kinaba: 		for(;;)
23dfcca431 2011-02-23        kinaba: 		{
524cc07867 2012-04-03        kinaba: 			// Dijkstra : find the "shortest path" from S to T wrt C[][].
524cc07867 2012-04-03        kinaba: 			//   C[][] can be <0 so we must be careful. Instead of computing the shortest path directly,
524cc07867 2012-04-03        kinaba: 			//   we compute the increase ("delta") from the shortest path in the previous iteration.
524cc07867 2012-04-03        kinaba: 			//   Since shortest path cannot decrease, delta is always >=0 when traversing edges.
524cc07867 2012-04-03        kinaba: 			//   Smallest delta implies smallest dist[T]+delta[T].
524cc07867 2012-04-03        kinaba: 			vector<Cost> delta(N, COST_INF); delta[S] = 0;
23dfcca431 2011-02-23        kinaba: 			vector<int>  prev(N, -1);
23dfcca431 2011-02-23        kinaba: 
524cc07867 2012-04-03        kinaba: 			typedef pair< Cost, pair<int, int> > cedge;
23dfcca431 2011-02-23        kinaba: 			priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
524cc07867 2012-04-03        kinaba: 			Q.push( cedge(0, make_pair(S, S)) );
23dfcca431 2011-02-23        kinaba: 			while( !Q.empty() ) {
524cc07867 2012-04-03        kinaba: 				const cedge e = Q.top(); Q.pop();
524cc07867 2012-04-03        kinaba: 				const int u_prev = e.second.first;
524cc07867 2012-04-03        kinaba: 				const int u = e.second.second;
524cc07867 2012-04-03        kinaba: 				if( prev[u] >= 0 ) // visited
23dfcca431 2011-02-23        kinaba: 					continue;
524cc07867 2012-04-03        kinaba: 				prev[u] = u_prev;
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 				for(int i=0; i<G[u].size(); ++i) {
524cc07867 2012-04-03        kinaba: 					const int  v = G[u][i];
524cc07867 2012-04-03        kinaba: 					const Cost v_delta = dist[u]+delta[u]+C[u][v] - dist[v];
524cc07867 2012-04-03        kinaba: 					if( F[u][v]>0 && delta[v]>v_delta )
524cc07867 2012-04-03        kinaba: 						Q.push( cedge(delta[v]=v_delta, make_pair(u,v)) );
23dfcca431 2011-02-23        kinaba: 				}
23dfcca431 2011-02-23        kinaba: 			}
23dfcca431 2011-02-23        kinaba: 
524cc07867 2012-04-03        kinaba: 			// If T is unreachable, finished.
23dfcca431 2011-02-23        kinaba: 			if( prev[T] < 0 )
524cc07867 2012-04-03        kinaba: 				break;
524cc07867 2012-04-03        kinaba: 
524cc07867 2012-04-03        kinaba: 			// Update the distance table.
524cc07867 2012-04-03        kinaba: 			for(int u=0; u<N; ++u)
524cc07867 2012-04-03        kinaba: 				if( delta[u] != COST_INF )
524cc07867 2012-04-03        kinaba: 					dist[u] += delta[u];
23dfcca431 2011-02-23        kinaba: 
524cc07867 2012-04-03        kinaba: 			// How much water can flow on the min-cost path?
524cc07867 2012-04-03        kinaba: 			Flow f = FLOW_INF;
23dfcca431 2011-02-23        kinaba: 			for(int u=T; u!=S; u=prev[u])
23dfcca431 2011-02-23        kinaba: 				f = min(f, F[prev[u]][u]);
23dfcca431 2011-02-23        kinaba: 
524cc07867 2012-04-03        kinaba: 			// Run the flow as much as possible
524cc07867 2012-04-03        kinaba: 			total_flow += f;
524cc07867 2012-04-03        kinaba: 			for(int u=T; u!=S; u=prev[u]) {
23dfcca431 2011-02-23        kinaba: 				total_cost    += f * C[prev[u]][u];
23dfcca431 2011-02-23        kinaba: 				F[prev[u]][u] -= f;
23dfcca431 2011-02-23        kinaba: 				F[u][prev[u]] += f;
23dfcca431 2011-02-23        kinaba: 			}
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 		return make_pair(total_cost, total_flow);
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: };