最小割树

前言

话说luogu题单真的好妙啊！！！看题单的时候看到了这个东西，这个东西讲真的比字符串多项式那些简单多了。。。

思想

最小割树的定义

给你一张图，每次查询两个点之间的最小割，你应该怎么做？

显然，每次都暴力跑一遍不是我们想要的答案。我们想要更快的方法，那我们应该怎么办呢？

我们想一下，在OI里面什么最好做。树！！！ 对呀，如果我们可以对于最小割构造出一棵树是不是就好做了呢？

我们定义最小割树为：

边权为原图上的最小割的一棵树，并且对于该树上的一条边$(s,t)$，去掉$(s,t)$这条边之后最小割树上的两棵子树为原图中去掉$(s,t)$的最小割的两个点集。

至于为什么，这就是人类智慧了，等会看到后面的性质应该自然就理解了。

最小割树的构造示例

对于这个问题，我们可以使用分治解决。

考虑对于下面这个图，我们如何构造出最小割树:

我们假如一开始选了$\text {A,E}$两个点，那么，它们之间的最小割就为$\text {DE}$。如下图:

那么，我们就可以在最小割树从$\text {A}$向$\text {E}$连一条长度为$4$的边。接着，我们就可以把这个图分成两部分:

然后我们再去分别考虑两个点集构造出的最小割树即可。在具体的图上就是继续考虑点集$\text {seta=\{A,B,C,D\}}$以及$\text {setb=\{E\}}$即可。

很显然，对于$\text {setb=\{E\}}$，什么都不需要干。

我们继续考虑$\text {seta=\{A,B,C,D\}}$，我们假设我们继续选$A，C$两点。很显然，最小割应该长成这个样子。

于是，我们就可以连一条$A\to C$边权为$12$的边。于是，我们继续分为点集$\{A,B,D\}$和$\{C\}$，显然，我们只需要考虑前一个点集。

显然，后面我们会连$A\to B$边权为$4$，$A\to D$边权为 $7$。因为太显然了，这里就不讲了。

最小割树构造流程

1. 找出最小割（最大流）。

2. 连边。

3. 根据残余网络连通性将代码分成$2$个点集继续考虑。

第$3$步其实就是找到去掉该边之后原图被分出来的两个点集。

最小割树的性质

两个点之间的最小割为最小割树上的两点之间边权最小值。

为了证明方便，我们定义$f(x,y)$为原图上$x\to y$的最小割。

---

在证明之前，我们有几个定理需要了解。

定理1

对于$q\in \text V_x,p\in \text V_y$，有$f(x,y)\geq f(q,p)$

证明

我们使用反证法。

假设$f(p,q)>f(x,y)$，那么，割去$x\to y$的最小割$p,q$依然联通（显然）。那么，就可以$x\to q\to p\to y$，显然与最小割矛盾。得证。

定理2

对于$x,y$，$\forall z$有$f(x,y)\geq \min\{f(x,z),f(z,y)\}$。

证明

因为最小割等于最大流，所以根据最大流的性质这是显然的。（我感觉我的好多东西都是显然啊！！！）

定理2推论

对于一个排列$p_1,p_2,..,p_k$，存在:

$$f(x,y)\geq \min\{f(x,p_1),f(p_1,p_2),...,f(p_k,y)\}$$

证明

根据定理2显然。

---

有了上面这些东西我们就可以推导了。

我们假设在最小割树上$(x,y)$之间路径之间权值最小值的端点为$(p,q)$，那么，根据定理2推论可以得到$f(x,y)\geq f(p,q)$，又根据最小割树性质可以得到$x,y$在$p,q$的两旁，所以根据定理1可以得到$f(p,q)\geq f(x,y)$。

综上，$f(p,q)=f(x,y)$。

例题讲解

其实最小割树真正有价值的题目并不是很多，重题似题真的没有必要做。

$\text {The 1st}$

题目传送门 【模板】最小割树

题目大意

给定一个$n$个点$m$条边的无向连通图，多次询问两点之间的最小割

$\text {Code}$

戳这里打开

$\text {The 2nd}$

题目传送门 CF343E Pumping Stations

题目大意

一个$n$个点$m$条边的无向图，求出一个排列$a_1,a_2,...,a_n$，使得:

$$\sum_{i=2} \text {mincut}(a_{i-1},a_i)$$

最大，其中，$\text {mincut(i,j)}$表示$i\to j$的最小割。

要求你输出最大值，以及排列$a$。

思路

这道题真的算是少有的比较灵活的应用了。

我们可以发现的是，在最小割树建好以后，一定每条边都会对答案产生影响（必定有两个点会经过此边），那么，最好情况就是每条边只会被计算一次。

虽然理论上这是可行的，但是我们还是需要把它构造出来。

我们还是考虑分治。假如我们现在需要对当前的子树构造出一个最优排列，那我们应该怎么做呢？

我们先找到边权最小的边，然后把该子树从此边分裂成两棵子树继续构造。那为什么这种方法正确性是对的呢？因为分裂出的子树$1$的末位和子树$2$的首位所产生的贡献必定是边权最小边。

边界条件也很简单，直接看还是否有子节点即可。

于是，当我们递归完整颗子树时，我们就可以得到排列了。

$\text {Code}$

戳这里打开

$\text{The 3rd}$

题目传送门

题目大意

有一个$n$个点$m$条边的无向图，每个点都有一个权值。

有$q$次查询，每次查询给出一个$k$,求出一个点集使得两两之间的不相交路径的最小值最大，并且该点集的权值之和不小于$k$。

思路

其实还是很妙的。

首先，我们思考如何求出两个点之间不相交路径条数。这个问题其实可以最大流解决，对于两个点连一条边权为$1$的边，两个点之间的最大流就是答案。

又因为最大流=最小割，于是，两个点之间不相交路径条数就可以使用最小割树查询出来。

然后。。。似乎没有什么头绪啊。。。

我们接着思考，在线似乎不太可行，我们可以把询问离线下来。

我们考虑枚举当前最小割为$w$的时候，显然，所有最小割树上边权比它大的都可以使用。对于当前可以使用的边，我们可以建出一个图。我们可以记录下来每个联通块的点权和(需要提醒的是，这些图上的联通块在原图上不一定是联通块)。

如果有联通块的权值和大于某个询问的$k$,那么，该询问的答案就一定不小于$w$。

考虑这样做为什么是对的，因为边权比它小的都不会出现，在当前合法的情况下一定最优，所以，显然。

$\text {Code}$

戳这里查看

$\text {The 4th}$

因为一些特殊原因需要之后才能展现出来。

upd on 2020-08-18：

它死掉了。。。。。。。。。。。。。。。。。。。。

参考博客

https://www.luogu.com.cn/blog/user38148/solution-p4897

https://www.luogu.com.cn/blog/Karry5307/solution-cf343e

https://www.luogu.com.cn/blog/Marser/solution-p3729