Gomory Hu Tree Implementation

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Gomory Hu Tree Implementation
Source            : 
Category          : Graph Theory
Algorithm         : Gomory Hu Tree, All pair maximum flow
Complexity        : O(n * T(maxflow))
Verdict           : Ok.

This implementation is for undirected graph.

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. #define ll          long long int  
6. #define inf         123456678890  
7.   
8. static const int maxn = 200 + 5;  
9.   
10. struct node  
11. {  
12.       int v, w;  
13.       node(int v = 0, int w = 0) : v(v), w(w) {}  
14. };  
15.   
16. vector <int> graph[maxn];  
17. vector <node> gomoryTree[maxn];  
18. int tnode, tedge;  
19. ll cap[maxn][maxn];   //capacity of the edge  
20. ll flow[maxn][maxn];  // total sending flow  
21. int level[maxn], ptr[maxn];  
22. int father[maxn]; // father of node i in Gumor-Hu tree  
23. ll maxflow[maxn];  
24.   
25. bool bfs(int source, int sink)  
26. {  
27.       fill(begin(level), end(level), -1);  
28.       queue <int> PQ;  
29.       PQ.push(source);  
30.       level[source] = 0;  
31.       while (!PQ.empty())  
32.       {  
33.             int u = PQ.front(); PQ.pop();  
34.             for (int v : graph[u])  
35.             {  
36.                   if (level[v] != -1 || flow[u][v] >= cap[u][v]) continue;  
37.                   level[v] = level[u] + 1;  
38.                   PQ.push(v);  
39.             }  
40.       }  
41.       return level[sink] != -1;  
42. }  
43.   
44. ll dfs(int u, ll minCap, int sink)  
45. {  
46.       if (u == sink) return minCap;  
47.       for (int &i = ptr[u]; i < (int)graph[u].size(); i++)  
48.       {  
49.             int v = graph[u][i];  
50.             if (level[v] == level[u]+1 && flow[u][v] < cap[u][v])  
51.             {  
52.                   ll minFlow = dfs(v, min(minCap, cap[u][v] - flow[u][v]), sink);  
53.                   if (minFlow > 0)  
54.                   {  
55.                         flow[u][v] += minFlow;  
56.                         flow[v][u] -= minFlow;  
57.                         return minFlow;  
58.                   }  
59.             }  
60.       }  
61.       return 0;  
62. }  
63.   
64. ll DinicMaxFlow(int source, int sink)  
65. {  
66.       int maxFlow = 0;  
67.       while(bfs(source, sink))  
68.       {  
69.             memset(ptr, 0, sizeof ptr);  
70.             while(ll bottleneck = dfs(source, inf, sink))  
71.             {  
72.                   maxFlow += bottleneck;  
73.             }  
74.       }  
75.       return maxFlow;  
76. }  
77.   
78. void setCapacity(int u, int v, ll cost)  
79. {  
80.       cap[u][v] = cost;  
81.       cap[v][u] = cost;  
82. }  
83.   
84. void addEdge(int u, int v)  
85. {  
86.       graph[u].push_back(v);  
87.       graph[v].push_back(u);  
88. }  
89.   
90. void clearFlow()  
91. {  
92.       for (int i = 0; i < maxn; i++)  
93.       {  
94.             for (int j = 0; j < maxn; j++)  
95.             {  
96.                   flow[i][j] = flow[j][i] = 0;  
97.             }  
98.       }  
99. }  
100.   
101. int main()  
102. {  
103.       freopen("in.txt", "r", stdin);  
104.   
105.       cin >> tnode >> tedge;  
106.       for (int e = 0; e < tedge; e++)  
107.       {  
108.             int u, v, w;  
109.             cin >> u >> v >> w;  
110.             u++, v++;  
111.             cerr << u << " " << v << endl;  
112.             addEdge(u, v);  
113.             setCapacity(u, v, w);  
114.       }  
115.       //       Construction of Gomory-Hu Tree  
116.       for (int i = 1; i <= tnode; i++) father[i] = 1;  
117.       for (int i = 2; i <= tnode; i++)  
118.       {  
119.             clearFlow();  
120.             maxflow[i] = DinicMaxFlow(i, father[i]);  
121.             bfs(i, father[i]);  
122.             for (int j = i+1; j <= tnode; j++)  
123.             {  
124.                   if (level[j] != -1 && father[j] == father[i]) father[j] = i;  
125.             }  
126.       }  
127.       // New Graph Creation  
128.       for (int i = 2; i <= tnode; i++)  
129.       {  
130.             gomoryTree[i].push_back(node(father[i], maxflow[i]));  
131.             gomoryTree[ father[i] ].push_back(node(i, maxflow[i]));  
132.             cout << i << " " << father[i] << " " << maxflow[i] << endl;  
133.       }  
134.       //              End  
135. }  
136.   
137. 6 11  
138. 0 1 10  
139. 0 5 8  
140. 1 5 3  
141. 1 2 4  
142. 1 4 2  
143. 2 5 2  
144. 2 4 4  
145. 2 3 5  
146. 3 5 2  
147. 3 4 7  
148. 4 5 3  
149.   
150. 2 1 18  
151. 3 2 13  
152. 4 3 14  
153. 5 3 15  
154. 6 2 17