原来一个很明显的错误程序，样例都通过不了，都AC了。。。

//这是那个论文，转载

最小割 Stoer-Wagner 算法 
Etrnls 2007-4-15 
Stoer-Wagner 算法用来求无向图 G=(V, E)的全局最小割。 
 
算法基于这样一个定理：对于任意s, t   V ∈ ，全局最小割或者等于原图的s-t 最小割，或者等于将原图进行 Contract(s, 
t)操作所得的图的全局最小割。 
 
算法框架： 
1. 设当前找到的最小割MinCut 为+∞  
2. 在 G中求出任意 s-t 最小割 c，MinCut = min(MinCut, c)   
3. 对 G作 Contract(s, t)操作，得到 G'=(V', E')，若|V'| > 1，则G=G'并转 2，否则MinCut 为原图的全局最
小割  
 
Contract 操作定义： 
若不存在边(p, q)，则定义边(p, q)权值w(p, q) = 0 
Contract(a, b): 删掉点 a, b 及边(a, b)，加入新节点 c，对于任意 v  V ∈ ，w(v, c) = w(c, v) = w(a, v) + w(b, 
v) 
 
求 G=(V, E)中任意 s-t 最小割的算法： 
定义w(A, x) = ∑w(v[i], x)，v[i]  A ∈  
定义 Ax 为在x 前加入 A 的所有点的集合（不包括 x）  
1. 令集合 A={a}，a为 V中任意点  
2. 选取 V - A中的 w(A, x)最大的点 x加入集合 A  
3. 若|A|=|V|，结束 
令倒数第二个加入 A的点为 s，最后一个加入 A的点为 t，则s-t 最小割为 w(At, t) 

• Re:数据有点问题（附Stoer-wagner详解） (840) 735612658 2012-03-01 19:06:21
• Re:数据有点问题（附Stoer-wagner详解） (840) chr32 2014-12-20 15:07:48