题解：P4897 【模板】最小割树（Gomory-Hu Tree）

Eznibuil · 2023-01-30 00:06:52 · 题解

Upd on 2023.3.1：些许补充和修复。

Upd on 2023.5.2：为了方便检测 Gomory-Hu 算法的正确性，造了一道板子。

Upd on 2024.5.6：修正定理 1 的证明错误。

Upd on 2024.9.13：题解区 KaTeX 升级，进行小修复。

前言：很难相信 Gomory-Hu Tree 的板子题没人写 Gomory-Hu 算法的题解。不过话说回来这题也没必要用 Gomory-Hu Tree。

写个更易懂（也许？）的 Gomory-Hu 算法的粗略证明放这里。不太清晰（毕竟本人也不怎么懂），若需要好一点的请参见参考文献[2]。

最小割树（Gomory-Hu Tree），满足原图上的两点间的最小割大小和方案正好有一种是树上对应两点间的最小割大小和方案。

下面定义：图 G=(V,E)，V 为点集，E 为边集，\lambda(x,y) 表示 x,y 之间的最小割。

Lemma 1

任取三点 a,b,c，有 \lambda(a,b)\ge\min(\lambda(a,c),\lambda(c,b))。

证明：考虑 a,b,c 之间的割：设切断 a\leftrightarrow b 和 a\leftrightarrow c 的最小的割权值是 \alpha，切断 a\leftrightarrow b 和 b\leftrightarrow c 的最小的割权值是 \beta，切断 a\leftrightarrow c 和 b\leftrightarrow c 的最小的割权值是 \gamma，则原式化为 \min(\alpha,\beta)\ge\min(\min(\alpha,\gamma),\min(\beta,\gamma))，得证。

由此可得 \lambda(a,b),\lambda(a,c),\lambda(b,c) 三者中必有两者相等，且另一个大于等于相等的两者。

然后立即得出以下推论：

Corollary 1

对于任意互不相同的 k 个点 s_1,s_2,\cdots,s_k\in V，有 \lambda(s_1,s_k)\ge\min(\lambda(s_1,s_2),\lambda(s_2,s_3),\cdots,\lambda(s_{k-1},s_k))。

Theorem 1

若一棵树的每条边满足边权为最小割且割断此边分出的点集与最小割割出的点集相同，那么取任意两点 u,v，令 s,t 为 u,v 的路径上最小的边，则 \lambda(u,v)=\lambda(s,t)。

证明：根据引理 1，\lambda(u,v)\ge\lambda(s,t)；另一方面，根据此树的定义，必然 s,t 的最小割可以成为 u,v 的割，有 \lambda(u,v)\le\lambda(s,t)。综上得证。

注：此树即为 Gomory-Hu Tree。

定义一个割 W（一边的点的点集）的权函数 \delta(W) 为所有满足一端点在 W 而另一端点不在 W 的边的边权和。

Lemma 2.1