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