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