最小割集Stoer-Wagner算法初探
首先抄一些网上关于该算法裸的解释:
1.min=MAXINT，固定一个顶点P
2.从点P用“类似”prim的s算法扩展出“最大生成树”，记录最后扩展的顶点和最后扩展的边
3.计算最后扩展到的顶点的切割值（即与此顶点相连的所有边权和），若比min小更新min
4.合并最后扩展的那条边的两个端点为一个顶点（当然他们的边也要合并，这个好理解吧？）
5.转到2，合并N-1次后结束
6.min即为所求，输出min
第一眼看到这么"精辟"的解释感到很蛋疼，画了很多图研究了好一会儿，突然发现解释地有点可爱。当然我并不是藐视这种解释，或许换个人看看会感觉解释地很自然，很清晰。
当然下面我就要解释一下它的可爱之处，和我对于该算法的理解。(这里我将采用混着论述的方法)
如果你对该算法要干什么不是很清楚请先看一下poj的2914 Minimum Cut ，题目连接：/problem?id=2914
目的：将图划分成S 和T两部分
算法主线：每次搜索完后便找到了当前的最小割，这时更新最小割的值，同时将该点扔进集合。
Step1: 算法开始，随便找一点P，然后从P开始累加和P点相连的边的连通度，并将它存储在wage[i]数组中，算法演示：
这里的wage初始值都为0
Step2: 这一步是keypoint ，而且也是我觉得网上的解释比较可爱的地方，在step1之后，就得到了相应的wage值，如果我们找到当前wage值最大的那个点(如果有多个这样的点那么任选其一)，那么这时候这个点也就是在已选了P点之后能获得的最大的连通度的点，按照这个思路我们依次进行这个步骤: 在未访问过的点中找wage值最大的点，那么当算法进行到结束的时候，这时我们获得了这样的两个点S 和T ，其中T是最后找到的那个点，S是T刚刚前一个找到的点。那么这时候就可以得到一条十分有用的性质:
wage[T] = 将T这个点分离这幅图的连通度之和，也就是说sum(T的连通度)
这条结论很容易证明：因为每次找到一个点u的时候都对和这个点相连的点v加上了一个从u到v的连通度g[u][v]（表示u,v之间点的连通度，即u，v有几条边连接），那么当当前的节点为T的时候，和T相连的所有的边的连通度必然都已经累加并存储在了wage[T]中。这时我可以不假思索地说wage[T]为S和T中较小的点的割集，要理解这一点可以看下面的两种情况(且只会出现这两种情况):
Condition 1 :
Condition 2 :
你可以自己先模拟一下上文提到过的步骤。
这里必须明确一点，那就在step2 中我们并不关心选出来的wage[T]是否是全局的最小割，
我们只关心wage[T]是S或者T中的最小割。以上面的两幅图来说就是，对于condition 1 由于S的选取早于T的选取也就是说在选择S或者T作为扩展的节点时，由于wage[S] >= wage[T] ，我们必须选S，接下来，如果当前节点是S那么无论是wage[S]还是wage[T]，都只剩下(2,3)这条边的连通度没有更新。那么到底是应该更新S还是T，很明显我们应该更新T，因为在更新(2,3)边之前wage[S] >= wage[T] , 如果我们更新wage[T]那么获得的割集肯定是两者中较小的。Condition 2 的情况分析于此类似（这里我就不再赘述了）。这里提及一下，前面说我感到网上的算法描述很可爱，主要是首先step2和最大生成树更本一点关系也没有，只是模仿了最大生成树构造方法而已(形似而神不似)。
Step3：由于step2我们已经获得了S和T中的最小割，并且更新了最小割的值那么不妨将T扔到集合in_set 中，表示对T求割值已经ok了。接下来提出一个绝妙的想法(当然不是我自己想出来的)，如果将S和T合并成一个点，并且更新S的相应元素的值，那么T便可以丢弃了。如果这条想法可行的话那么点的规模便会减小。只要扫描n - 1次便可以得到最终的解。下面证明一下其可行性。再次回到上面的两幅图，对于condition 1 ，只需将T移向S和S重合，那么原来和T相连的边，现在和S也相连了，这时候T和S在同一个连通块中，那么及时删去T也不会对后面的操作产生影响，原因：既然wage[T]表示S和T中的最小割，那么最小割必然不会是wage[S] + (S->T的连通度) , 而且我已经更新了最小割的值，那么现在即使将S和T合并也不会影响全局最小割的求解。而对于condition 2 的解释更加简单。Condition 2 中当当前扫描到的节点是T，那么wage[S] , wage[T]中已经保存了S和T 两个单节点的累计连通度之和。所以当将S和T合并之时，已经将T独立了，而S和T中的最小割又不是wage[T] 那么，将S和T合并，并不会影响后面的计算。
好了就三步可以得出最小割了，时间复杂度为O(n^3) 或者O(n^2logn).
总结：keypoint: 处理的时候始终是对单点求最小割，多点的最小割通过合并可以转化成单点的最小割。
Code (Stoer-WagnerO(n^3)) :
typedef long long Type;
bool in_set[cy] , vis[cy];
Type wage[cy];
Type Search ( int n , int &S , int &T ){
memset ( vis , false , n * sizeof ( vis[0] ) );
memset ( wage , 0 , n * sizeof ( wage[0] ) );
S = T = -1;
Type min_cut ;
int u = 0;
for ( int i = 0 ; i < n ; i++ ){
Type mx = -INF;
for ( int j = 0 ; j < n ; j++ ){
if ( !in_set[j] && !vis[j] && mx < wage[j] ){
mx = wage[u = j];
}
