最小割树 学习笔记

# 最小割树 ## 前言 话说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}$ [题目传送门 【模板】最小割树](https://www.luogu.com.cn/problem/P4897) ### 题目大意 给定一个$n$个点$m$条边的无向连通图，多次询问两点之间的最小割 ### $\text {Code}$ [戳这里打开](https://www.luogu.com.cn/paste/ufc36wsr) ### $\text {The 2nd}$ [题目传送门 CF343E Pumping Stations](https://www.luogu.com.cn/problem/CF343E) ### 题目大意 一个$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}$ [戳这里打开](https://www.luogu.com.cn/paste/yb7xt7ca) ### $\text{The 3rd}$ [题目传送门](https://www.luogu.com.cn/problem/P3729) ### 题目大意 有一个$n$个点$m$条边的无向图，每个点都有一个权值。 有$q$次查询，每次查询给出一个$k$,求出一个点集使得两两之间的不相交路径的最小值最大，并且该点集的权值之和不小于$k$。 ### 思路 其实还是很妙的。 首先，我们思考如何求出两个点之间不相交路径条数。这个问题其实可以最大流解决，对于两个点连一条边权为$1$的边，两个点之间的最大流就是答案。 又因为最大流=最小割，于是，两个点之间不相交路径条数就可以使用最小割树查询出来。 然后。。。似乎没有什么头绪啊。。。 我们接着思考，在线似乎不太可行，我们可以把询问离线下来。 我们考虑枚举当前最小割为$w$的时候，显然，所有最小割树上边权比它大的都可以使用。对于当前可以使用的边，我们可以建出一个图。我们可以记录下来每个联通块的点权和(需要提醒的是，这些图上的联通块在原图上不一定是联通块)。 如果有联通块的权值和大于某个询问的$k$,那么，该询问的答案就一定不小于$w$。 考虑这样做为什么是对的，因为边权比它小的都不会出现，在当前合法的情况下一定最优，所以，显然。 ### $\text {Code}$ [戳这里查看](https://www.luogu.com.cn/paste/om4rjvic) ### $\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