|
| 1 | +#Gomory Hu Tree |
| 2 | + |
| 3 | +##Definition |
| 4 | + |
| 5 | +The gomory-hu tree of an undirected graph with capacities consists of a weighted tree that condenses information from all the*s-t cuts* for all s-t vertex pairs in the graph. Naively, one must think that $O(|V|^2)$ flow computations are needed to build this data structure, but actually it can be shown that only $|V| - 1$ flow computations are needed. Once the tree is constructed, we can get the minimum cut between two vertices*s* and*t* by querying the minimum weight edge in the unique*s-t* path. |
| 6 | + |
| 7 | +##Gusfield's Simplification Algorithm |
| 8 | + |
| 9 | +We can say that two cuts (X, Y) and (U, V)*cross* if all four set intersections $X \cup U$, $X \cup V$, $Y \cup U$, $Y \cup V$ are nonempty. Most of the work of the original gomory-hu method is involved in maintaining the noncrossing condition. The following simpler, yet efficient method, proposed by Gusfield uses crossing cuts to produce equivalent flow trees. |
| 10 | + |
| 11 | +##Complexity |
| 12 | + |
| 13 | +The algorithm total complexity is $\mathcal{O}(V*MaxFlow)$, wich means that the overall complexity depends on the algorithm that was choosen to find the maximum flow. |
| 14 | + |
| 15 | +###Implementation |
| 16 | +This implementation considers the Gomory-Hu tree as a struct with methods: |
| 17 | + |
| 18 | +- The maximum flow algorithm must also be a struct with methods, in the implementation bellow we utilize Dinic's algorithm to calculate the maximum flow. |
| 19 | + |
| 20 | +- The algorithm is 0-indexed and will root the tree in node 0. |
| 21 | + |
| 22 | +- The method*solve* returns the list of edges of the Gomory-Hu tree. |
| 23 | + |
| 24 | +```{.cpp file=gomoryhu} |
| 25 | +structgomory_hu { |
| 26 | +struct edg{ |
| 27 | +int u, v, cap; |
| 28 | +}; |
| 29 | + |
| 30 | +Dinic dinic; // you can change your Max Flow algorithm here |
| 31 | +// !! if you change remember to make it compatible with the rest of the code !! |
| 32 | + |
| 33 | +vector<edg> edgs; |
| 34 | + |
| 35 | +void add_edge(int u, int v, int cap) { // the edges are already bidirectional |
| 36 | +edgs.push_back({u, v, cap}); |
| 37 | +} |
| 38 | + |
| 39 | +vector<int> vis; |
| 40 | + |
| 41 | +voiddfs(int a) { |
| 42 | +if (vis[a]) return; |
| 43 | +vis[a] = 1; |
| 44 | +for (auto &e : dinic.adj[a]) |
| 45 | +if (e.c - e.flow() > 0) |
| 46 | +dfs(e.to); |
| 47 | +} |
| 48 | + |
| 49 | +vector<pair<ll, int>> solve(int n) { |
| 50 | +vector<pair<ll, int>> tree_edges(n); // if i > 0, stores pair(cost, parent). |
| 51 | + |
| 52 | +for (int i = 1; i < n; i++) { |
| 53 | +dinic = Dinic(n); |
| 54 | + |
| 55 | +for (auto &e : edgs) dinic.addEdge(e.u, e.v, e.cap); |
| 56 | +tree_edges[i].first = dinic.calc(i, tree_edges[i].second); |
| 57 | +
|
| 58 | +vis.assign(n, 0); |
| 59 | +dfs(i); |
| 60 | + |
| 61 | +for (int j = i + 1; j < n; j++) { |
| 62 | +if (tree_edges[j].second == tree_edges[i].second && vis[j]) |
| 63 | +tree_edges[j].second = i; |
| 64 | +} |
| 65 | +} |
| 66 | + |
| 67 | +return tree_edges; |
| 68 | +} |
| 69 | +}; |
| 70 | +``` |
| 71 | +
|
| 72 | +## Task examples |
| 73 | +
|
| 74 | +Here are some examples of problems related to the Gomory-Hu tree: |
| 75 | +
|
| 76 | +- Given a weighted and connected graph, find the minimun s-t cut for all pair of vertices. |
| 77 | +
|
| 78 | +- Given a weighted and connected graph, find the minimum/maximum s-t cut among all pair of vertices. |
| 79 | +
|
| 80 | +- Find an approximate solution for the [Minimum K-Cut problem](https://en.wikipedia.org/wiki/Minimum_k-cut). |
| 81 | +
|
| 82 | +## Practice Problems |
| 83 | +
|
| 84 | +- [Codeforces - Juice Junctions](https://codeforces.com/gym/101480/attachments) |
| 85 | +
|
| 86 | +- [Codeforces - Honeycomb](https://codeforces.com/gym/103652/problem/D) |
| 87 | +
|
| 88 | +- [Codeforces - Pumping Stations](https://codeforces.com/contest/343/problem/E) |