Artifact 27b1f3ac721526bcf53951c370bf5b826f25f0f7
//-------------------------------------------------------------
// Stoer-Wagner
// Minimum cost for making the graph unconnected
// O(V^3)
//
// G : bidirectional (G[v][u] == G[u][v])
//
// Verified by
// - SRM 340 Div1 LV3
//-------------------------------------------------------------
typedef int cost;
typedef int vert;
typedef vector< vector<cost> > graph;
cost bidi_minCut( graph G, int N )
{
vector<vert> V;
for(int v=0; v<N; ++v)
V.push_back(v);
cost result = 0x7fffffff;
for(int n=N; n>1; --n)
{
// invariant:
// the current set of vertices = {V[0] .. V[n-1]}
// order the vertices
// v0 = 0 (arbitrary),
// v1 = (u that maximizes \Sigma G[v0][u])
// v2 = (u that maximizes \Sigma G[v0][u]+G[v1][u])
// ...
// vn-2
// vn-1 = (maximizes lastCut = \Sigma G[v0][u]+G[vn-2][u])
vector<int> vs;
cost lastCut = 0;
{
vector<cost> ws(n, 0);
ws[0] = 1;
for(int i=0; i<n; ++i) {
int j = max_element(ws.begin(), ws.end()) - ws.begin();
lastCut = ws[j];
vs.push_back(j);
ws[j] = -1;
for(int k=0; k<n; ++k)
if( ws[k] != -1 )
ws[k] += G[V[k]][V[j]];
}
}
// update mincut
// lemma: "the min cost for separating vn-2 and vn-1"==lastCut
result = min(result, lastCut);
// reduce the graph (unify vn-2 and vn-1)
// for testing the case vn-2 and vn-1 is connected
vert v2=vs[n-2], v1=vs[n-1];
for(int i=0; i<n; ++i) {
G[V[v2]][V[i]] += G[V[v1]][V[i]];
G[V[i]][V[v2]] += G[V[i]][V[v1]];
}
V.erase( V.begin() + v1 );
}
return result;
}