一种极其好写的非递归式严格最小割树

· · 算法·理论

本文介绍的算法来自：王文涛 2016 年国集论文《浅谈无向图最小割问题的一些算法及应用》。

ChatGPT 5.6 协助了本文的编写。

吐槽

最小割树的洛谷模板的题解区中，大部分题解写的都不是严格的最小割树（Gomory-Hu 树），而是等价流树。这种树虽然满足任意两点 u,v 在树上路径的最小边权等于 (u,v) 的最小割值，但不能直接从树边恢复对应的最小割方案。

而能构造方案的 Gomory-Hu 树的递归写法实现又过于复杂（需要进行点的收缩）。

好在原论文中给出了一种非递归式的写法，实现简单，但理解起来较为复杂。本文会先直接给出实现，再给出独立于递归式写法的证明。

文末还给出了一组 Hack 数据，用于说明等价流树得到的结果不一定满足 Gomory-Hu 树的严格性质。

一些规定

对于大多数题解实现的等价流树，其满足上面这个结论但不满足删去 (s,t) 的边之后两个连通块恰好是 (s,t) 的一个最小割。故称其为“非严格”的最小割树。

实现

维护两个数组 fa 和 val，表示每个点在树上的父亲，以及其到父亲这条边的边权。初始 \forall i\in[1,n]，fa_i=0,val_i=-1，表示所有点暂时挂在 0 号点上，且边权还未确定。

遍历 s=1\sim n，依次执行如下步骤：

  1. 设 t=fa_s。

  2. 求出 (s,t) 的任意一个最小割 \delta(S)，s\in S,t\in V-S，将 val_s\leftarrow \lambda(s,t)。

  3. 遍历所有 fa_v=t 的点 v（即所有 s 的兄弟），若 v\in S，则将 fa_v\leftarrow s，val_v 不变。

  4. 若 t>0，设 p=fa_t，此时若 p\in S，则将 fa_t\leftarrow s，fa_s\leftarrow p，并交换 val_s,val_t。

整个过程结束后，对于 i=1\sim n，建立边 (i,fa_i,val_i)。即 fa_i 就是固定 0 为根的一棵最小割树上，i 号点的父亲，val_i 就是 (i,fa_i) 的边权。

我们声称这样建出来的树就是一棵 Gomory-Hu 树。整个流程时间复杂度 O(n\times maxflow)。

:::info[核心代码]

为了方便，实现中令 fa_0=0。

采用 dinic 算法实现了最小割，其中 dis_j\neq -1 相当于 j 和 s 在最小割同侧。

for (int s = 1; s <= n; s++) {
    int t = f[s];
    val[s] = mincut(s, t);
    for (int j = 1; j <= n; j++)
        if (j != s && f[j] == f[s] && ~dis[j])
            f[j] = s;
    int p = f[t];
    if (~dis[p]) {
        f[t] = s, f[s] = p;
        swap(val[s], val[t]);
    }
}

:::

证明

一些重要引理&定理

引理 1：对于任意不同的三点 u,v,w，\lambda(u,w)\ge \min(\lambda(u,v),\lambda(v,w))。

证明：随便取一个 (u,w) 的最小割 \alpha(u,w)，此时 v 在 u 侧则 \lambda(u,w)\ge \lambda(v,w)，否则 \lambda(u,w)\ge \lambda(u,v)。

推论 1：对于任意不同的两点 u,v，有 \lambda(u,v)\ge\min(\lambda(u,w_1),\lambda(w_1,w_2),\dots,\lambda(w_k,v))。

引理 2：对于任意 A,B\subseteq V，d(A)+d(B)\ge d(A\cup B)+d(A\cap B)，即函数 d 的子模性。

证明：按顶点是否属于 A,B 分为四个区域，对于一条边，只需讨论两顶点位于不同区域的 6 种情况，每种情况对不等式两边的贡献。

:::info[更容易的理解方式] 画出论文中类似的图： :::

引理 3：对于任意 A,B\subseteq V，d(A)+d(B)\ge d(A\backslash B)+d(B\backslash A)。其中 A \backslash B 表示 \{x|x\in A\land x\notin B\}，即 A\cap V-B。

证明：对 A 和 V-B 使用引理 2，重要等式：d(A)=d(V-A)。

定理 4（uncrossing）：对于两点 s,t 的一个最小割 \alpha(s,t)，设其 s 的一侧为 W，则对于所有不同的 u,v\in W，存在 (u,v) 的一个最小割 \delta(Y)，使得 Y\subseteq W。

证明：设 \delta(X) 是 (u,v) 的一个最小割，不妨设 u,s\in X，分 t\notin X 和 t\in X 两种情况讨论：

这个 uncrossing 是接下来证明中非常重要的一个工具。

做法拆解

我们在维护什么？

假设目前处理完 s，则对于所有 1\le u\le s，保证了以 u 为根的子树恰好构成某个 (u,fa_u) 的最小割中包含 u 的一侧，并且 val_u=\lambda(u,fa_u)。

处理完 s=n 时，我们就成功构建了一棵最小割树。

:::info[回顾我们的做法] 遍历 s=1\sim n，依次执行如下步骤：

  1. 设 t=fa_s。

  2. 求出 (s,t) 的任意一个最小割 \delta(S)，s\in S,t\in V-S，将 val_s\leftarrow \lambda(s,t)。

  3. 遍历所有 fa_v=t 的点 v（即所有 s 的兄弟），若 v\in S，则将 fa_v\leftarrow s，val_v 不变。

  4. 若 t>0，设 p=fa_t，此时若 p\in S，则将 fa_t\leftarrow s，fa_s\leftarrow p，并交换 val_s,val_t。

整个过程结束后，对于 i=1\sim n，建立边 (i,fa_i,val_i)。即 fa_i 就是固定 0 为根的一棵最小割树上，i 号点的父亲，val_i 就是 (i,fa_i) 的边权。 :::

我们需要在处理 s 时，解释以下问题：

对于兄弟

首先对于那些 v>s 的兄弟，只要在 S 中就直接接到 s 下面，由于这些点都还没有被处理过，子树内也没有点，所以这步操作不会破坏维护的结构。

对于 v<s 的那些兄弟，设 X=subtree(v)，显然 \delta(X) 是 (v,t) 的一个最小割。此时 S 把 X 切成了两部分，我们的目标是利用 uncrossing，把 S 调整为与 X 不交或包含。分类讨论 v 是否在 S 中：

情况 1： v\notin S

类似 uncrossing 的证法，可以证明 d(S)=d(S \backslash X)，于是我们可以把 S 调整为 S \backslash X，对应到实现就是保持 fa_v 不变。

情况 2：v\in S

同样地，我们可以把 S 调整为 S\cup X 并不改变最小割。对应到实现上就是把 v 的子树接到 s 下，即令 fa_v\leftarrow s。

接下来还有一个问题，为什么此时 val_v 不用变化，即 \lambda(v,t)=\lambda(v,s)？

根据引理 1，\lambda(v,s)\ge\min( \lambda(v,t),\lambda(s,t))。

因为 \delta(S) 也是 (v,t) 的一个割，因此 \lambda(s,t)\ge \lambda(v,t)，得到 \lambda(v,s)\ge \lambda(v,t)。

又因为 \delta(X) 也是 (v,s) 的一个割，因此 \lambda(v,t)\ge\lambda(v,s)。

综上，\lambda(v,t)=\lambda(v,s)。

对于父亲

设 Y=subtree(t)，仍是按 p 是否在 S 中分类讨论。

情况 1：p\notin S

和刚才的 v\notin S 一样，可以把 S 调整为 S\cap Y，实现上就是不做改变。

情况 2：p\in S

可以把 S 调整为 S\cup V-Y，即让 t 的子树外全部归到 s 侧。即让下图中红色部分和紫色部分在边 (s,t) 的 s 一侧，而蓝色部分在另一侧。

这时候就可以让 fa_s\leftarrow p，fa_t\leftarrow s，相当于一次 "rotate"：

         p
         |
         t
      /  |  \
not-S    s   not-S
        / \
      S     S

变成

   p
   |
   s
/  |  \
S   S    t
      /   \
   not-S not-S

对于边权：

由于 s 从 t 的儿子变成了 t 的父亲，所以 val_t=\lambda(s,t)，也就是原来的 val_s。

所以只需要证明 \lambda(s,p)=\lambda(t,p)，就可以说明 val_s 可以使用原来的 val_t，对应到实现就是交换原来的 val_s,val_t。

和刚刚证明边权相等的部分一样，根据引理 1，\lambda(s,p)\ge\min( \lambda(s,t),\lambda(t,p))。

因为 \delta(S) 也是 (t,p) 的一个割，因此 \lambda(s,t)\ge \lambda(t,p)，得到 \lambda(s,p)\ge \lambda(t,p)。

又因为 \delta(Y) 也是 (s,p) 的一个割，因此 \lambda(t,p)\ge\lambda(s,p)。

综上，\lambda(s,p)=\lambda(t,p)。

于是，整个做法的正确性得到了证明。

Hack

以题解区 @_LHF_ 的代码为例，给出如下数据：

2 3
0 1 1
1 2 2
2 0 2

代码建出来的树是：

0-----1-----2
   3     3

但对于删除 (1,2) 边后得到的割 (\{2\},\{0,1\}) 的权为 4，并不是 (1,2) 之间的最小割。

事实上这张图的唯一一种 Gomory-Hu 树应该形如：

0-----2-----1
   3     3

这个 Hack 仅仅是针对于这份代码的写法。实际上在大多数题解实现的等价流树算法中，每次递归选取的两点不同，最后建出来的树也会不同。但只需改变这个 Hack 中节点的编号顺序，大概率仍能起到效果。

感谢大家百忙之中阅读这篇文章。