STOER-WAGNER 无源无汇最小割
问题
一个无向联通图,应该要正边权?，最小割分成两个子图
方法
引理
图G中的两个点s,t,
如果最小割分割了它们，那么直接求s到t的最小割
如果没有，那么合并s-t，得到的新图G1 和原图的最小割一致
因此有方法, 任意选择点a，加入集合A中
每次选择和A距离和最大的点加入集合中，也就是上面的合并操作
注意，这里每次都不是把图里的最大的边去掉，而是集合A距离最大的点加入A中
这样反复操作，一直到剩下3个点A,b,c ，可以得到一个割的值, 除了A以外的两个点b,c在这次分割中一定是被分开了的
我们也能得到一个b和c是被分割的值
重新初始的图
合并 b和c成集合B
重复上面所有操作，直到剩余3个点，B,d,e
重新初始的图
合并b,c成集合B, 合并d和e成集合D
重复上面所有操作，直到剩余3个点，?a,?b,?c,
我们能到到一个分割值，也能让下一轮的操作合并两个点
这样我们最终所有操作中最小的分割就是答案
Proof
对于 每一轮剩余3个点的时候，我们有该轮的初始集合S，和另外两点$p_1,p_2$
因为合并规则一直是与S距离最大的边，所以$p_1,p_2$ 一定是被分割的，
虽然因为边的长度可能在操作过程中相等，也就意味着在每一轮操作开始时，甚至$p_1,p_2$ 是哪两个点，是不确定的,(当然我们可以给所有点提前编号，保持即使值相等的点也有一定的偏序关系，来让结果唯一)
但是可以证明，对于每次计算到剩余3个点时，其中的$p_1,p_2$来说，当前图里面这是这两个点要切割的最小割
我们把这轮的$(p_1,p_2)$ 命作$(s,t)$
对于给定图$G$，和通过上述步骤得到的$s,t$
如果两个点之间没有相连，我们在数值上可以看做有一条相连权重为0的边,在下面的计算上没有影响(因为每次取得是最大的), 连通的判断时权重为0视为不连通
割: 把原图分成两个联通块的边集
$C$是$G$上$s-t$的一个任意的割,即$s,t$在不同连通块
$CP$是按照上述步骤得到的$s-t$的割
$W(边集)$ = 边集的权重和
$W(点集A，点v)$ = $点v$到$点集A$中所有点的边权和
要证:$W(C) \ge W(CP)$
对于上述给定流程$CP$，根据点加入的顺序，命名为$a_1,a_2,a_3…a_{n-1},a_n$, 其中$s = a_{n-1},t = a_n$
对于 $i$,如果$a_{< i-1}$和$a_{i}$ 位于 割C的两侧,那么称为$i$为$active$的(简化后面描述)
- 我们不用讨论$CP$，因为序列就是$CP$产生的，所有操作都是位于$CP$割的同一连通块
点集 $A_i = 集合(a_1…a_{i-1}) $
也就是$a_i$前面的点
边集 $C_i = 集合(边|边的两端均属于集合(a_1…a_i)) ∩ C$
也就是割边中，端点都在前面$a_1..a_i$ 中
我们要证明对于每一个$active$的$i$, $W(A_i, a_i) \le W(C_i)$,
也就是$a_i$和它之前的点的边权和 小于 割$C$中的两端来自前$a_1 … a_i$的边权和
接下来归纳开始 (归纳的目标和总目标一致)
初始: 若$i$是最小使得$active$的，那么$W(A_i,a_i) = W(C_i)$
因为 说明 前面的边,按照割C，都在同一侧，所以$C_i$中所有的边，都一个顶点是$a_i$
对于$i,j,(i < j)$ 都是$active$相邻
$i$和$j$是active, $i$和$j$之间没有其它$active$的,
$W(A_j,a_j) = W(A_i,a_j) + W(A_j - A_i, a_j) $
直接的拆分点集$A_j$
$\le W(C_i) + W(A_j - A_i, a_j) $
根据初始条件和归纳,$W(A_i,a_j)\le W(A_i,a_i) \le W(C_i)$ , 前一半不等式是操作过程中每次选最大距离的连通，后一部分是归纳
$= W(C_j)$
因为$i$和$j$之间没有其它$active$，所以也就是$i$和$j$之间的点不会与小于$j$的点构成属于$C_u$的边，
而对于$W(A_j-A_i,a_j)$的贡献，不会和$C_i$重复因为(不包含$a_j$),
综上
$W(A_n,a_n) \le W(C_n) = W(C)$
左边不等式是归纳的结果，右边是因为所有C中的边且两端的点在所有点中，就是$C$自己
结论:
也就是说，对于图$G$的$s-t$任何的割$C$，都不小于$t$单独划分出来的边权和
所以这是一个最小分割
回到操作过程
也就是每一轮，都能产生$s-t$分割的最小割，之后的轮次，$s$和$t$就在同一个“连通块”里了
这里有一点 实际上再思考仔细一点，这个过程中其实并不满足题意(分成两个)，因为我们很可能把原图分割成了好几个连通块，也就是不止两个。但是因为如果能分割成多个，反向操作，每次最多把两个合成一个，必定最小割是分成两个的。所以得到的答案也一定是割, 保证了正确性
也就是你合并的s和t可能，它们还并不连通，只不过你从划分上认为属于一块了
综上，算法正确性证毕
Ref
https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm