23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: //------------------------------------------------------------- 23dfcca431 2011-02-23 kinaba: // Gomory-Hu 23dfcca431 2011-02-23 kinaba: // All Pair Minimum Cuts for an Undirected Graph 23dfcca431 2011-02-23 kinaba: // O(V^4) 23dfcca431 2011-02-23 kinaba: // 23dfcca431 2011-02-23 kinaba: // G : undirected (G[i].has(j) <==> G[j].has(i)) 23dfcca431 2011-02-23 kinaba: // F : flow-capacity F[i][j] = F[j][i] = Capacity 23dfcca431 2011-02-23 kinaba: // 23dfcca431 2011-02-23 kinaba: // Verified by 23dfcca431 2011-02-23 kinaba: // - CodeCraft 09 CUTS 23dfcca431 2011-02-23 kinaba: //------------------------------------------------------------- 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: static const int NV = 512; 23dfcca431 2011-02-23 kinaba: typedef int flow; 23dfcca431 2011-02-23 kinaba: typedef int vert; 23dfcca431 2011-02-23 kinaba: typedef vert edge; 23dfcca431 2011-02-23 kinaba: typedef vector<edge> edges; 23dfcca431 2011-02-23 kinaba: typedef vector<edges> graph; 23dfcca431 2011-02-23 kinaba: typedef flow flow_graph[NV][NV]; 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: flow_graph GHF; 23dfcca431 2011-02-23 kinaba: void GomoryHu( graph& G, flow_graph F, flow_graph AllPairMinCut ) 23dfcca431 2011-02-23 kinaba: { 23dfcca431 2011-02-23 kinaba: int N = G.size(); 23dfcca431 2011-02-23 kinaba: vector<vert> parent(N, 0); 23dfcca431 2011-02-23 kinaba: vector<flow> weight(N, 0); 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: // construct the Gomory-Hu Tree 23dfcca431 2011-02-23 kinaba: for(vert s=1; s<N; ++s) 23dfcca431 2011-02-23 kinaba: { 23dfcca431 2011-02-23 kinaba: vert t = parent[s]; 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: // mincut between s and t 23dfcca431 2011-02-23 kinaba: memcpy(GHF, F, sizeof(GHF)); 23dfcca431 2011-02-23 kinaba: flow mincut = 0; 23dfcca431 2011-02-23 kinaba: for(;;) { 23dfcca431 2011-02-23 kinaba: // bfs 23dfcca431 2011-02-23 kinaba: vector<vert> prev(N, -1); prev[s]=s; 23dfcca431 2011-02-23 kinaba: queue<vert> Q; Q.push(s); 23dfcca431 2011-02-23 kinaba: while( !Q.empty() ) { 23dfcca431 2011-02-23 kinaba: vert v = Q.front(); Q.pop(); 23dfcca431 2011-02-23 kinaba: for(int i=0; i<G[v].size(); ++i) { 23dfcca431 2011-02-23 kinaba: vert u = G[v][i]; 23dfcca431 2011-02-23 kinaba: if( prev[u]==-1 && GHF[v][u] ) 23dfcca431 2011-02-23 kinaba: prev[u]=v, Q.push(u); 23dfcca431 2011-02-23 kinaba: } 23dfcca431 2011-02-23 kinaba: } 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: if( prev[t] == -1 ) 23dfcca431 2011-02-23 kinaba: { 23dfcca431 2011-02-23 kinaba: // done: separeted to {v|prev[v]!=-1} and {v|prev[v]==-1} 23dfcca431 2011-02-23 kinaba: // split t's children 23dfcca431 2011-02-23 kinaba: weight[s] = mincut; 23dfcca431 2011-02-23 kinaba: for(vert v=0; v<N; ++v) 23dfcca431 2011-02-23 kinaba: if( parent[v]==t && prev[v]!=-1 && v!=s ) 23dfcca431 2011-02-23 kinaba: parent[v] = s; 23dfcca431 2011-02-23 kinaba: vert pt = parent[t]; 23dfcca431 2011-02-23 kinaba: if( prev[pt]!=-1 ) 23dfcca431 2011-02-23 kinaba: parent[s]=pt, parent[t]=s, weight[s]=weight[t], weight[t]=mincut; 23dfcca431 2011-02-23 kinaba: break; 23dfcca431 2011-02-23 kinaba: } 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: // flow... 23dfcca431 2011-02-23 kinaba: flow cur = 0x7fffffff; 23dfcca431 2011-02-23 kinaba: for(vert v=t; v!=s; v=prev[v]) 23dfcca431 2011-02-23 kinaba: cur = min(cur, GHF[prev[v]][v]); 23dfcca431 2011-02-23 kinaba: for(vert v=t; v!=s; v=prev[v]) 23dfcca431 2011-02-23 kinaba: GHF[prev[v]][v] -= cur, GHF[v][prev[v]] += cur; 23dfcca431 2011-02-23 kinaba: mincut += cur; 23dfcca431 2011-02-23 kinaba: } 23dfcca431 2011-02-23 kinaba: } 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: // AllPairMinCuts over the G-H tree 23dfcca431 2011-02-23 kinaba: for(vert s=0; s<N; ++s) { 23dfcca431 2011-02-23 kinaba: vector<vert> ps_s; 23dfcca431 2011-02-23 kinaba: for(vert v=s ;; v=parent[v]) 23dfcca431 2011-02-23 kinaba: { ps_s.push_back(v); if( v==parent[v] ) break; } 23dfcca431 2011-02-23 kinaba: reverse(ps_s.begin(), ps_s.end()); 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: for(vert t=s+1; t<N; ++t) { 23dfcca431 2011-02-23 kinaba: vector<vert> ps_t; 23dfcca431 2011-02-23 kinaba: for(vert v=t ;; v=parent[v]) 23dfcca431 2011-02-23 kinaba: { ps_t.push_back(v); if( v==parent[v] ) break; } 23dfcca431 2011-02-23 kinaba: reverse(ps_t.begin(), ps_t.end()); 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: vert ca; 23dfcca431 2011-02-23 kinaba: for(int i=0; i<ps_s.size() && i<ps_t.size() && ps_s[i]==ps_t[i]; ++i) 23dfcca431 2011-02-23 kinaba: ca = ps_s[i]; 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: flow s_to_root = 0x7fffffff, t_to_root = 0x7fffffff; 23dfcca431 2011-02-23 kinaba: for(vert v=s; v!=ca; v=parent[v]) 23dfcca431 2011-02-23 kinaba: s_to_root = min(s_to_root, weight[v]); 23dfcca431 2011-02-23 kinaba: for(vert v=t; v!=ca; v=parent[v]) 23dfcca431 2011-02-23 kinaba: t_to_root = min(t_to_root, weight[v]); 23dfcca431 2011-02-23 kinaba: AllPairMinCut[s][t] = AllPairMinCut[t][s] = min(s_to_root, t_to_root); 23dfcca431 2011-02-23 kinaba: } 23dfcca431 2011-02-23 kinaba: } 23dfcca431 2011-02-23 kinaba: }