加载中…
个人资料
夜晚的虫子
夜晚的虫子
  • 博客等级:
  • 博客积分:0
  • 博客访问:15,233
  • 关注人气:3
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

最小割 Stoer-Wagner 算法

(2011-06-09 20:31:37)
标签:

最小割

stoer-wagner

算法

poj

pku

2914

杂谈

分类: C语言

最小割Stoer-Wagner算法

 

割:在一个图GVE)中V是点集,E是边集。在E中去掉一个边集C使得GVE-C)不连通,C就是图GVE)的一个割;

最小割:GVE)的所有割中,边权总和最小的割就是最小割。

 

G的任意s-t最小割Min-Cst):

st是途中的两个点且边(st)∈E(即st之间存在一条边)。如果G的最小割CutG分成MN两个点集

①:如果sMtNMin-Cst= Cut(不讨论)

②:如果stM(或者stN)则Min-Cst<= Cut

 

我们来定义一个Contract(a,b)操作,即把ab两个点合并,表示为删除节点b,把b的节点信息添加到a

如下图是做了Contract5,6

最小割 <wbr>Stoer-Wagner <wbr>算法

最小割 <wbr>Stoer-Wagner <wbr>算法

对于所点vw(v,5)+=w(v,6)

 

s-t最小割的方法

定义w(A,x) = ∑w(v[i],x)v[i]∈A

定义Ax为在x前加入A的所有点的集合(不包括x

1.令集合A={a}aV中任意点

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为例,图为

 

 

 

 

 

 

 

 

最小割 <wbr>Stoer-Wagner <wbr>算法

GVE

我们设法维护这样的一个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)的权值aA

记录最后加入A的节点为t=6,倒数第二个加入A的为s=5,则s-t的最小割就为w[s],在图中体现出来的意思就是5-6的最小割为w[s]=3

然后我们做Contract(s,t)操作,得到下图

最小割 <wbr>Stoer-Wagner <wbr>算法

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=5t=7    s-t最小割是4

Contract(s,t)得到

最小割 <wbr>Stoer-Wagner <wbr>算法

 

 

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=4t=5    s-t最小割是4

Contract(s,t)得到

最小割 <wbr>Stoer-Wagner <wbr>算法


 

 

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=3t=4    s-t最小割是2,(此时已经得出答案,以下省略)

 

AC代码:

 #include <iostream>

#include <stdio.h>

#include <string.h>

#include <queue>

 

#define INT_MAX 0x3f3f3f3f

 

using namespace std;

 

int mp[502][502];

int N,M;

bool combine[502];

int minC=INT_MAX;

 

void search(int &s,int &t){

    bool vis[502];

    int w[502];

    memset(vis,0,sizeof(vis));

    memset(w,0,sizeof(w));

    int tmpj=1000;

    for(int i=0;i<N;i++){

        int max=-INT_MAX;

        for(int j=0;j<N;j++){

            if(!vis[j]&&!combine[j]&&max<w[j]){

                max=w[j];

                tmpj=j;

            }

        }

        if(t==tmpj){minC=w[t];return;}

        vis[tmpj]=1;

        s=t,t=tmpj;

        for(int j=0;j<N;j++){

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

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

        }

    }

    minC=w[t];

}

 

int mincut(){

    int ans=INT_MAX;

    int s,t;

    memset(combine,0,sizeof(combine));

    for(int i=0;i<N-1;i++){

        s=t=-1;

        search(s,t);

        combine[t]=true;

        ans=ans>minC?minC:ans;

        for(int j=0;j<N;j++){

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

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

        }

    }

    return ans;

}

 

int main(){

    //freopen("in.txt","r",stdin);

    while(cin>>N>>M){

        memset(mp,0,sizeof(mp));

        int u,v,w;

        while(M--){

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

            mp[u][v]+=w;

            mp[v][u]+=w;

        }

        cout<<mincut()<<endl;

    }

    return 0;

}

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有