GomoryHu

Given a list of edges representing an undirected flow graph, returns edges of the Gomory-Hu tree. The max flow between any pair of vertices is given by minimum edge weight along the Gomory-Hu tree path.

Time: O(V) Flow Computations 13 lines Tested on CERC 2015 J, stress-tested

Needs: "PushRelabel.h"

content/graph/GomoryHu.h — chilli, Takanori MAEHARA, source: https://github.com/spaghetti-source/algorithm/blob/master/graph/gomory_hu_tree.cc#L102

typedef array<ll, 3> Edge;
vector<Edge> gomoryHu(int N, vector<Edge> ed) {
	vector<Edge> tree;
	vi par(N);
	rep(i,1,N) {
		PushRelabel D(N); // Dinic also works
		for (Edge t : ed) D.addEdge(t[0], t[1], t[2], t[2]);
		tree.push_back({i, par[i], D.calc(i, par[i])});
		rep(j,i+1,N)
			if (par[j] == par[i] && D.leftOfMinCut(j)) par[j] = i;
	}
	return tree;
}