23dfcca431 2011-02-23 kinaba: //------------------------------------------------------------- 23dfcca431 2011-02-23 kinaba: // MinCost-MaxFlow 23dfcca431 2011-02-23 kinaba: // O(??) 23dfcca431 2011-02-23 kinaba: // 23dfcca431 2011-02-23 kinaba: // Verified by 23dfcca431 2011-02-23 kinaba: // - SRM 487 Div2 LV3 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_); 23dfcca431 2011-02-23 kinaba: static const Cost COST_INF = 1e+300; // !!EDIT HERE!! 23dfcca431 2011-02-23 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; 23dfcca431 2011-02-23 kinaba: vector<Cost> h(N, 0); // potential 23dfcca431 2011-02-23 kinaba: for(Flow RF=FLOW_INF; RF>0; ) // residual flow 23dfcca431 2011-02-23 kinaba: { 23dfcca431 2011-02-23 kinaba: // Dijkstra -- find the min-cost path 23dfcca431 2011-02-23 kinaba: vector<Cost> d(N, COST_INF); d[S] = 0; 23dfcca431 2011-02-23 kinaba: vector<int> prev(N, -1); 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: typedef pair< Cost, pair<int,int> > cedge; 23dfcca431 2011-02-23 kinaba: priority_queue< cedge, vector<cedge>, greater<cedge> > Q; 23dfcca431 2011-02-23 kinaba: Q.push( cedge(0, make_pair(S,S)) ); 23dfcca431 2011-02-23 kinaba: while( !Q.empty() ) { 23dfcca431 2011-02-23 kinaba: cedge e = Q.top(); Q.pop(); 23dfcca431 2011-02-23 kinaba: if( prev[e.second.second] >= 0 ) 23dfcca431 2011-02-23 kinaba: continue; 23dfcca431 2011-02-23 kinaba: prev[e.second.second] = e.second.first; 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: int u = e.second.second; 23dfcca431 2011-02-23 kinaba: for(int i=0; i<G[u].size(); ++i) { 23dfcca431 2011-02-23 kinaba: int v = G[u][i]; 23dfcca431 2011-02-23 kinaba: Cost r_cost = C[u][v] + h[u] - h[v]; 23dfcca431 2011-02-23 kinaba: if( F[u][v] > 0 && d[v] > d[u]+r_cost ) 23dfcca431 2011-02-23 kinaba: Q.push( cedge(d[v]=d[u]+r_cost, make_pair(u,v)) ); 23dfcca431 2011-02-23 kinaba: } 23dfcca431 2011-02-23 kinaba: } 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: if( prev[T] < 0 ) 23dfcca431 2011-02-23 kinaba: break; // Finished 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: // Run the flow as much as possible 23dfcca431 2011-02-23 kinaba: Flow f = RF; 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: RF -= f; 23dfcca431 2011-02-23 kinaba: total_flow += f; 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: for(int u=T; u!=S; u=prev[u]) 23dfcca431 2011-02-23 kinaba: { 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: // Update the potential 23dfcca431 2011-02-23 kinaba: for(int u=0; u<N; ++u) 23dfcca431 2011-02-23 kinaba: h[u] += d[u]; 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: };