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