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;
}
};