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