最小割树 学习笔记

问题描述

给定一张图，求任意两点的最小割。要求跑 \(n\) 次最大流。

做法

暴力需要跑 \(n^2\) 次最大流，然而这样很浪费，因为求出 \(u, v\) 两点的最小割以后，我们还获得了至少一种最小割方案，可以通过这一方案获得更多信息。注意到假设通过最小割断开后，\(s, t\) 所在集合分别为 \(S, T\)，则对于所有 \(u\in S, v\in T\)，\(u, v\) 之间的最小割不会超过当前的最小割。考虑怎么利用这个性质。

给出集合的某种划分，使得任意一个横跨划分的点对都具有某种性质，这样的信息会导出某种树结构。在这个问题中，导出的树结构被称为 最小割树。具体地，每次对于一个点集合，选择任意两个点作为源、汇点，求 原图上的 最小割，以这个最小割的大小为边权，在当前源汇点之间连边，然后将点集划分，递归处理。可以证明，这样得到一棵树，对于两个点 \(u, v\)，它们之间的最小割小于等于树上路径上边权的最小值；除此之外，还可以得出它们之间的最大流大于等于树上路径边权最小值。由最大流等于最小割，可以得到这两个点之间的最小割就是树上路径边权最小值。