发现自己完全不会最小割树,于是来学一学.
概念
一张 $n$ 个点的图上,两点之间只存在 $n-1$ 种本质不同的最小割.
可以构造出一棵带边权的树,满足树上两点的最小割 (即两点路径上最小边权) 等于原图上两点最小割.
这样的树称为最小割树,也称 Gomory-Hu Tree .
构造方法
先任意选取两个节点 $u,v$ ,求出它们的最小割 ${\rm cut}(u,v)$ ,跑最大流时,满流的边就对应最小割中割掉的边.
通过这组割,可以把图划分成两个部分, $u$ 所在的点集记作 $U$ , $v$ 所在的点集记作 $V$ .
对于任意 $x\in U,y\in V$ ,有 ${\rm cut}(x,y)\le {\rm cut}(u,v)$ .
否则用 ${\rm cut}(u,v)$ 的花费一定无法割开 $x,y$ ,也就割不开 $u,v$ ,就矛盾了.
在最小割树上新建一条边 $(u,v)$ ,边权为 ${\rm cut}(u,v)$ ,然后对点集 $U,V$ 内的点分别递归执行以上算法.
最后恰好计算了 $n-1$ 次最小割,也建出了最小割树.
考虑树上路径 $x\to y$ 经过的每条边 $u\to v$ .
那么在建出 $u\to v$ 这条边时, $x,y$ 被分入了不同集合,有 ${\rm cut}(x,y)\le {\rm cut}(u,v)$ .
简单归纳就可以得到这样的构造满足了概念中的性质,即,树上两点路径上最小边权等于原图上两点最小割.
那么我们只做了 $O(n)$ 次最小割,就可以支持询问任意两点之间的最小割了.