最小割树（Gomory-Hu Tree）是一种可以在 \(O(Vf)\) 的时间里求出一个图中全源最小割的算法，其中 \(f\) 为一次最大流的时间。
记原图为 \(G=(V,E)\)，其最小割树为 \(G'=(V,E')\).
在最小割树中，任两点间的最小割等于它们在原图中的最小割，且 \(\forall (u, v) \in E'\)，\(E' \setminus \{u, v\}\) 将 \(V\) 分割成的两个集合等于 \(u,v\) 最小割将 \(V\) 分割成的两个集合。
算法流程：在当前点集 \(V_\text{now}\) 中选两个点 \(u,v\)，求出它们在 \(G\) 中的最小割，在 \(G'\) 中将 \(u, v\) 连边，权为割的值。同时，求出最小割将 \(V_\text{now}\) 分成的两个集合，将它们作为新一轮的 \(V_\text{now}\) 递归求解，这两个集合中的点在 \(G'\) 中以 \((u,v)\) 连接。
边界条件：\(\left\vert V_{\text{now}} \right\vert = 1\)，此时直接返回。
感性证明：当某一步把 \(u,v\) 划分到两个 \(V_{\text{now}}\) 中时，\(u,v\) 的最小割 \(\le\) 此时的最小割。
总共要跑 \(V-1\) 次最大流，因此时间复杂度是 \(O(Vf)\) 的。
code:
auto &ans(int x, int y){ return x>y ? ans_[y][x] : ans_[x][y]; }
int vis[N];
void dfs(int x){
for(int i=flow::head[x+1]; i; i=flow::es[i].nxt){
if(flow::es[i].lf > 0 && !vis[flow::es[i].to-1]){
vis[flow::es[i].to-1] = 1;
dfs(flow::es[i].to-1);
}
}
}
void gomory_hu(int *l, int *r){
if(l == r-1) return;
flow::reset();
flow::maxflow(*l, *(r-1));
ans(*l, *(r-1)) = flow::maxf;
std::fill(vis, vis+in, 0);
dfs(*l);
int *lp = l+1, *rp = r-2;
while(lp <= rp){
if(vis[*lp]) lp++;
else std::swap(*lp, *rp), rp--;
}
gomory_hu(l, lp);
gomory_hu(lp, r);
UP(i, l, lp) UP(j, lp, r){
ans(*i, *j) = std::min({
ans(*i, *l), ans(*l, *(r-1)), ans(*j, *(r-1))
});
}
}