最小割树

前言

话说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边权为

## 最小割树构造流程 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