最小割Stoer-Wagner算法
割：在一个图G（V，E）中V是点集，E是边集。在E中去掉一个边集C使得G（V，E-C）不连通，C就是图G（V，E）的一个割；
最小割：在G（V，E）的所有割中，边权总和最小的割就是最小割。
求G的任意s-t最小割Min-C（s，t）：
设s，t是途中的两个点且边（s，t）∈E（即s，t之间存在一条边）。如果G的最小割Cut把G分成M，N两个点集
①：如果s∈M，t∈N则Min-C（s，t）= Cut（不讨论）
②：如果s，t∈M（或者s，t∈N）则Min-C（s，t）<= Cut
我们来定义一个Contract(a,b)操作，即把a，b两个点合并，表示为删除节点b，把b的节点信息添加到a上,如下图是做了Contract（5,6）
对于所点v有w(v,5)+=w(v,6)
求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加入集合
3.若|A|=|V|，结束，否则更新w(A,x)，转到2
令倒数第二个加入A的点为s，最后一个加入A的点为t，则s-t最小割为w(At,t)
以Poj (pku) 2914 Minimum Cut
的第三个case为例，图为
G（V，E）
我们设法维护这样的一个w[]，初始化为0；
我们把V-A中的点中w[i]最大的点找出来加入A集合；
V-A直到为空
w[]的情况如下
|
w[i] |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
初始值 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
A=A∪{0} |
--- |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
A=A∪{1} |
|
--- |
2 |
2 |
1 |
0 |
0 |
0 |
|
A=A∪{2} |
|
|
--- |
3 |
1 |
0 |
0 |
0 |
|
A=A∪{3} |
|
|
|
--- |
1 |
0 |
0 |
1 |
|
A=A∪{4} |
|
|
|
|
--- |
1 |
1 |
2 |
|
A=A∪{7} |
|
|
|
|
|
2 |
2 |
--- |
|
A=A∪{5} |
|
|
|
|
|
--- |
3 |
|
|
A=A∪{6} |
|
|
|
|
|
|
--- |
|
每次w[i]+=∑(i,a)的权值a∈A
记录最后加入A的节点为t=6，倒数第二个加入A的为s=5，则s-t的最小割就为w[s]，在图中体现出来的意思就是5-6的最小割为w[s]=3
然后我们做Contract(s,t)操作，得到下图
G(V’,E’)
重复上述操作
|
w[i] |
0 |
1 |
2 |
3 |
4 |
5 |
7 |
|
初始值 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
A=A∪{0} |
--- |
1 |
1 |
1 |
1 |
0 |
0 |
|
A=A∪{1} |
|
--- |
2 |
2 |
1 |
0 |
0 |
|
A=A∪{2} |
|
|
--- |
3 |
1 |
0 |
0 |
|
A=A∪{3} |
|
|
|
--- |
1 |
0 |
1 |
|
A=A∪{4} |
|
|
|
|
--- |
2 |
2 |
|
A=A∪{5} |
|
|
|
|
|
--- |
4 |
|
A=A∪{7} |
|
|
|
|
|
|
--- |
s=5，t=7 s-t最小割是4
Contract(s,t)得到
|
w[i] |
0 |
1 |
2 |
3 |
4 |
5 |
|
初始值 |
0 |
0 |
0 |
0 |
0 |
0 |
|
A=A∪{0} |
--- |
1 |
1 |
1 |
1 |
0 |
|
A=A∪{1} |
|
--- |
2 |
2 |
1 |
0 |
|
A=A∪{2} |
|
|
--- |
3 |
1 |
0 |
|
A=A∪{3} |
|
|
|
--- |
1 |
1 |
|
A=A∪{4} |
|
|
|
|
--- |
4 |
|
A=A∪{5} |
|
|
|
|
|
--- |
s=4，t=5 s-t最小割是4
Contract(s,t)得到
|
w[i] |
0 |
1 |
2 |
3 |
4 |
|
初始值 |
0 |
0 |
0 |
0 |
0 |
|
A=A∪{0} |
--- |
1 |
1 |
1 |
1 |
|
A=A∪{1} |
|
--- |
2 |
2 |
1 |
|
A=A∪{2} |
|
|
--- |
3 |
1 |
|
A=A∪{3} |
|
|
|
--- |
2 |
|
A=A∪{4} |
|
|
|
|
--- |
s=3，t=4 s-t最小割是2，（此时已经得出答案，以下省略）
AC代码
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 using namespace std; 17 const int maxn = 510; 18 int e[maxn][maxn],n,m; 19 bool comb[maxn]; 20 int Find(int &s,int &t){ 21 bool vis[maxn]; 22 int w[maxn]; 23 memset(vis,false,sizeof(vis)); 24 memset(w,0,sizeof(w)); 25 int tmp = INF; 26 for(int i = 0; i < n; ++i){ 27 int theMax = -INF; 28 for(int j = 0; j < n; j++) 29 if(!vis[j] && !comb[j] && w[j] > theMax) 30 theMax = w[tmp = j]; 31 if(t == tmp) break; 32 s = t; 33 vis[t = tmp] = true; 34 for(int j = 0; j < n; j++) 35 if(!vis[j] && !comb[j]) 36 w[j] += e[t][j]; 37 } 38 return w[t]; 39 } 40 int solve(){ 41 int ans = INF,s,t; 42 memset(comb,0,sizeof(comb)); 43 for(int i = 1; i < n; i++){ 44 s = t = -1; 45 ans = min(ans,Find(s,t)); 46 for(int j = 0; j < n; j++){ 47 e[s][j] += e[t][j]; 48 e[j][s] += e[j][t]; 49 } 50 comb[t] = true; 51 } 52 return ans; 53 } 54 int main() { 55 int u,v,w; 56 while(~scanf("%d %d",&n,&m)){ 57 memset(e,0,sizeof(e)); 58 while(m--){ 59 scanf("%d %d %d",&u,&v,&w); 60 e[u][v] += w; 61 e[v][u] += w; 62 } 63 printf("%d ",solve()); 64 } 65 return 0; 66 }
转载自http://blog.sina.com.cn/s/blog_700906660100v7vb.html