最小割Stoer-Wagner算法

最小割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代码

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #include <stack>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn = ;

 int e[maxn][maxn],n,m;

 bool comb[maxn];

 int Find(int &s,int &t){

     bool vis[maxn];

     int w[maxn];

     memset(vis,false,sizeof(vis));

     memset(w,,sizeof(w));

     int tmp = INF;

     for(int i = ; i < n; ++i){

         int theMax = -INF;

         for(int j = ; j < n; j++)

             if(!vis[j] && !comb[j] && w[j] > theMax)

                 theMax = w[tmp = j];

         if(t == tmp) break;

         s = t;

         vis[t = tmp] = true;

         for(int j = ; j < n; j++)

             if(!vis[j] && !comb[j])

                 w[j] += e[t][j];

     }

     return w[t];

 }

 int solve(){

     int ans = INF,s,t;

     memset(comb,,sizeof(comb));

     for(int i = ; i < n; i++){

         s = t = -;

         ans = min(ans,Find(s,t));

         for(int j = ; j < n; j++){

             e[s][j] += e[t][j];

             e[j][s] += e[j][t];

         }

         comb[t] = true;

     }

     return ans;

 }

 int main() {

     int u,v,w;

     while(~scanf("%d %d",&n,&m)){

         memset(e,,sizeof(e));

         while(m--){

             scanf("%d %d %d",&u,&v,&w);

             e[u][v] += w;

             e[v][u] += w;

         }

         printf("%d\n",solve());

     }

     return ;

 }

转载自http://blog.sina.com.cn/s/blog_700906660100v7vb.html

巴特西

最小割Stoer-Wagner算法

最新文章

热门文章