最小割树学习笔记

Wmd_125 · 2025-10-16 22:34:06 · 算法·理论

前言

似乎距离上次写学习笔记已经过去了很久很久，上一篇学习笔记还是回文自动机学习笔记。这段时间其实也学了不少东西但一直没时间写，今天就趁着稍微有点的时间来写写。

问题引入

给你一个 n 个点 m 条边的无向连通图，边有非负边权，给定两个点 u,v，每次可以花费那条边边权的代价将这条边断开，问使得点 u,v 不联通的最小代价。
n\le 200,m\le 5000

我相信聪明的你一定发现这是道水题，好吧，确实。这就是经典的最小割问题，你可以从这里拷一份代码下来飞速做出这道题。但如果我们加上多组询问呢？

给你一个 n 个点 m 条边的无向连通图，边有非负边权，你可以花费一条边边权的代价将这条边断开，有 q 次询问，每次给定两个点 u,v，问使得点 u,v 不联通的最小代价。
n\le 500,m\le 1500,q\le 10^5

~~为什么 n 还更大了~~

其实就是这道题。

好的，普通的最小割已经无法帮我们解决这道题了，我们考虑预处理一些东西来帮助我们快速求出最小割。

算法讲解

Gomory-Hu Tree 是一种将图上最小割问题转化为树上问题的算法。

简单来说，这个算法就是构造一颗 n 个节点带边权的树，使得任意两点在原图上的最小割为树上两点简单路径上的最小边权。

那在讲算法流程之前我们先来证明一些等会要用的结论。

为了简便一点，我们定义 f(u,v) 为在原图上 u,v 两点的最小割代价。

定理 1

任取原图上互不相同的三个点 x,y,z。一定满足 f(x,y)\geq \min \lbrace f(x,z),f(y,z)\rbrace。

证明如下：

因为我们只考虑这三个点，所以如果要将点 x,y 割开的话，点 z 一定会和点 x 或者点 y 在一个连通块里。简单分类讨论一下即可证明。

并由此我们可以得出以下推论：

对于任意 k 个互不相同的点构成的序列 s，一定满足下面的式子：

f(s_1,s_k)\ge \min \{f(s_1,s_2),f(s_2,s_3),\dots f(s_{k-2},s_{k-1}),f(s_{k-1},s_k)\}

证明如下：

注意到上面的式子是有顺序的，不是随意两个组合起来。尝试构造一个使得右式最大的情况。先不考虑右式的最后一项，那么右式就和 s_k 无关了。假如我们已经构造出了这么一张图，s_1 到 s_{k-1} 都是联通的，那么现在连上点 s_k，如果 s_k 连上了 s_1，那么一定满足 f(s_1,s_k)\ge f(s_{k-1},s_k)。连上其他点情况类似。

如果在这张图上 s_k 是割点，也就是说在不考虑 s_k 时 s_1 到 s_{k-1} 是不联通的，那么一定存在至少一对点分别在点 s_k 的两侧。简单分讨一下也可以得出结论。

好的，请确保以上定理及推论看懂了。接下来最重要的定理也是基于这个证明的。

定理 2

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

可以看得出来，这颗树就是我们上面提到的 Gomory-Hu Tree。

证明如下：

根据上面定理的推论，我们有 f(u,v)\ge f(s,t)。且根据这颗树的定义，s,t 的最小割一定可以使 u,v 之间断开，所以我们有 f(u,v)\le f(s,t)。综上，只能 f(u,v)=f(s,t)。

根据上面两个定理我们已经可以做题了。

算法流程

每次随便找两个在同一联通块内的点，在原图上跑一遍最小割。
在残量网络上看看哪些边被割开了，根据这些被割开的边将该联通块重新分为两个小联通块。并在树上将这两个点之间连一条边，边权设为最小割的代价即可。
这样一直分下去，直到连通块大小为 1 就结束操作。

让我们来分析一下时间复杂度，用 Dinic 跑一遍最小割的时间复杂度为 O(n^2m)，我们一共会跑 O(n) 次最小割，所以总时间复杂度为 O(n^3m)。已经十分优秀了。

至于例题中的多组询问，我们可以直接暴力 O(qn) 宽搜，如果你担心太暴力过不去的话就打个倍增，这样时间复杂度就是 O(q\log n) 的了。