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