Artifact 08ac17a6157e8d09cf98835de13eeb57fe4bf28b
//-------------------------------------------------------------
// Gomory-Hu
// All Pair Minimum Cuts for an Undirected Graph
// O(V^4)
//
// G : undirected (G[i].has(j) <==> G[j].has(i))
// F : flow-capacity F[i][j] = F[j][i] = Capacity
//
// Verified by
// - CodeCraft 09 CUTS
//-------------------------------------------------------------
static const int NV = 512;
typedef int flow;
typedef int vert;
typedef vert edge;
typedef vector<edge> edges;
typedef vector<edges> graph;
typedef flow flow_graph[NV][NV];
flow_graph GHF;
void GomoryHu( graph& G, flow_graph F, flow_graph AllPairMinCut )
{
int N = G.size();
vector<vert> parent(N, 0);
vector<flow> weight(N, 0);
// construct the Gomory-Hu Tree
for(vert s=1; s<N; ++s)
{
vert t = parent[s];
// mincut between s and t
memcpy(GHF, F, sizeof(GHF));
flow mincut = 0;
for(;;) {
// bfs
vector<vert> prev(N, -1); prev[s]=s;
queue<vert> Q; Q.push(s);
while( !Q.empty() ) {
vert v = Q.front(); Q.pop();
for(int i=0; i<G[v].size(); ++i) {
vert u = G[v][i];
if( prev[u]==-1 && GHF[v][u] )
prev[u]=v, Q.push(u);
}
}
if( prev[t] == -1 )
{
// done: separeted to {v|prev[v]!=-1} and {v|prev[v]==-1}
// split t's children
weight[s] = mincut;
for(vert v=0; v<N; ++v)
if( parent[v]==t && prev[v]!=-1 && v!=s )
parent[v] = s;
vert pt = parent[t];
if( prev[pt]!=-1 )
parent[s]=pt, parent[t]=s, weight[s]=weight[t], weight[t]=mincut;
break;
}
// flow...
flow cur = 0x7fffffff;
for(vert v=t; v!=s; v=prev[v])
cur = min(cur, GHF[prev[v]][v]);
for(vert v=t; v!=s; v=prev[v])
GHF[prev[v]][v] -= cur, GHF[v][prev[v]] += cur;
mincut += cur;
}
}
// AllPairMinCuts over the G-H tree
for(vert s=0; s<N; ++s) {
vector<vert> ps_s;
for(vert v=s ;; v=parent[v])
{ ps_s.push_back(v); if( v==parent[v] ) break; }
reverse(ps_s.begin(), ps_s.end());
for(vert t=s+1; t<N; ++t) {
vector<vert> ps_t;
for(vert v=t ;; v=parent[v])
{ ps_t.push_back(v); if( v==parent[v] ) break; }
reverse(ps_t.begin(), ps_t.end());
vert ca;
for(int i=0; i<ps_s.size() && i<ps_t.size() && ps_s[i]==ps_t[i]; ++i)
ca = ps_s[i];
flow s_to_root = 0x7fffffff, t_to_root = 0x7fffffff;
for(vert v=s; v!=ca; v=parent[v])
s_to_root = min(s_to_root, weight[v]);
for(vert v=t; v!=ca; v=parent[v])
t_to_root = min(t_to_root, weight[v]);
AllPairMinCut[s][t] = AllPairMinCut[t][s] = min(s_to_root, t_to_root);
}
}
}