poj 2914(stoer_wanger算法求全局最小割)

By | 08月26日
Advertisement

题目链接:http://poj.org/problem?id=2914

思路:算法基于这样一个定理:对于任意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)。

贴下大牛的模版:

poj 2914(stoer_wanger算法求全局最小割)
poj 2914(stoer_wanger算法求全局最小割)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAXN 555
 7 #define inf 1<<30
 8
 9 int v[MAXN],dist[MAXN];
10 int map[MAXN][MAXN];
11 bool vis[MAXN];
12 int n,m;
13
14 //求全局最小割的Stoer_Wanger算法
15 int Stoer_Wanger(int n)
16 {
17     int res=inf;
18     for(int i=0;i<n;i++)v[i]=i;
19     while(n>1){
20         int k=0,pre=0;//pre用来表示之前加入A集合的点,我们每次都以0点为第一个加入A集合的点
21         memset(vis,false,sizeof(vis));
22         memset(dist,0,sizeof(dist));
23         for(int i=1;i<n;i++){
24             k=-1;
25             for(int j=1;j<n;j++){
26                 if(!vis[v[j]]){
27                     dist[v[j]]+=map[v[pre]][v[j]];//dis数组用来表示该点与A集合中所有点之间的边的长度之和
28                     if(k==-1||dist[v[k]]<dist[v[j]]){
29                         k=j;
30                     }
31                 }
32             }
33             vis[v[k]]=true;
34             if(i==n-1){
35                 res=min(res,dist[v[k]]);
36                 //将该点合并到pre上,相应的边权就要合并
37                 for(int j=0;j<n;j++){
38                     map[v[pre]][v[j]]+=map[v[j]][v[k]];
39                     map[v[j]][v[pre]]+=map[v[j]][v[k]];
40                 }
41                 v[k]=v[--n];//删除最后一个点
42             }
43             pre=k;
44         }
45     }
46     return res;
47 }
48
49 int main()
50 {
51     int u,v,w;
52     while(~scanf("%d%d",&n,&m)){
53         memset(map,0,sizeof(map));
54         while(m--){
55             scanf("%d%d%d",&u,&v,&w);
56             map[u][v]+=w;
57             map[v][u]+=w;
58         }
59         int ans=Stoer_Wanger(n);
60         printf("%d\n",ans);
61     }
62     return 0;
63 }

View Code

Similar Posts:

  • poj 2914 Minimum Cut(全局最小割)

    题目大意:给你一个无相图,求出一个最小的割,使得原图不连通. 明显的全局最小割的裸题,用到了一个叫做SW算法的东西 就是每次在图中找到一个割s-t,C,然后用C去更新答案,然后在图中把s,t两个点合并,当最后图只有一个点时就可以了 证明也没看懂 #include<cstdio> #include<cstring> #include<cstring> #include<iostream> #include<algorithm> using name

  • Stoer-Wagner算法(O(n^3))求全局最小割 hdu3691 2010福州站B题

    这题比赛时没有做出来,一直以来都没有想到是全局最小割,现在看了别人的解题报告... 题意:给一图,入口,求将哪个点设为出口,使得最大流最小 分析:一直没有看出来是最小割集,想到那了还是蛮好理解的.http://wenku.baidu.com/view/7545db0d76c66137ee0619bd.html //求去掉最少的边使连通集划分为两连通集 就是用Stoer-Wagner算法(O(n^3))求最小的割集 #include<iostream> using namespace std;

  • POJ2914 Minimum Cut(全局最小割Stoer_Wagner算法:模板)

    全局最小割,这里有篇讲得很好的论文: http://www.cnblogs.com/ylfdrib/archive/2010/08/17/1801784.html 1 #include<algorithm> 2 #include<stdio.h> 3 #include<string.h> 4 using namespace std; 5 const int maxn = 1010; 6 /* 7 Stoer-Wagner算法:全局最小割 8 复杂度:N^2 9 邻接矩阵

  • ZOJ 2753 Min Cut (Destroy Trade Net)(无向图全局最小割)

    题目大意 给一个无向图,包含 N 个点和 M 条边,问最少删掉多少条边使得图分为不连通的两个部分,图中有重边 数据范围:2<=N<=500, 0<=M<=N*(N-1)/2 做法分析 典型的无向图全局最小割,使用 Stoer-Wagner 算法 Stoer-Wagner 算法共执行 n-1 次 BFS,每次 BFS 得到一个当前图的最小 S-T 割,并且将最后 BFS 的两个点缩点,n-1 次 BFS 得到 n-1 个最小 S-T 割中的最小者就是整个无向图的全局最小割,为了讲述每

  • 全局最小割模板

    一个无向连通网络,去掉一个边集可以使其变成两个连通分量则这个边集就是割集:最小割集当然就权和最小的割集. 可以用最小切割最大流定理: 1.min=MAXINT,确定一个源点 2.枚举汇点 3.计算最大流,并确定当前源汇的最小割集,若比min小更新min 4.转到2直到枚举完毕 5.min即为所求输出min 不难看出复杂度很高:枚举汇点要O(n),最短增广路最大流算法求最大流是O((n^2)m)复杂度,在复杂网络中O(m)=O(n^2),算法总复杂度就是O(n^5):哪怕采用最高标号预进流算法求最

  • 【POJ】3469 Dual Core CPU 最小割——项目分配问题

    传送门:[POJ]3469 Dual Core CPU 题目分析:刚才HDU4307不是白过的T U T..这题一看就知道是项目分配问题了,太让人感动了... 还是这个函数: 现在就是赤裸裸的用了~ 假设每个任务i在核心A上执行Xi取1,在核心B上执行Xi取0. 同时假设与源点相连的是Xi取1的,与汇点相连的是Xi取0的. 那么,现在我们建立源点S,汇点T,对所有的Xi建边S->Xi,Xi->T,表示Xi还不清楚分配给哪个核心执行. 由公式可知Xi选择1会产生ai的花费,Xi选择0会产生bi的

  • POJ 3204 Ikki&#39;s Story I | 最小割

    当时看题意都看错了,而且还以为就是求割边的条数,结果证明我是错的.后来多亏铭神帮我重新看了下题意并且还自己敲了一发. 题意: 一个小王国,n个城市中只有一个城市生产日常用品,因此要从该城市运送产品到首都,每条路径(有向)都有容量限制. 国王想加大产品的运送量,但王国的资金不足,国王只能选择一条路进行扩容. 问共有几条路增大流量后,最大流也增大的. 思路: 首先建好图求出原始状态的最大流,然后从残留网络中把所有源点s能到达的点标记下来,记为大S. 再从汇点t 用bfs进行往回广搜.广搜到属于S的点

  • poj 2914

    这是一道求全局最小割的题目,可以用Stoer Wagner算法.题目很短,但是有一点不要混乱了,就是这里权值代表两点间边的条数,所以要区分好是权值还是真的边数.这题要求权值最小的割集. 下面是Stoer Wagner算法的介绍(摘自:http://poj.org/showmessage?message_id=117503): Stoer-Wagner 算法用来求无向图 G=(V, E)的全局最小割. 算法基于这样一个定理:对于任意s, t  ∈V ,全局最小割或者等于原图的s-t 最小割,或者等

  • 图论 最小割Toer-Wagner算法

    参考来源:http://blog.sina.com.cn/s/blog_700906660100v7vb.html 这里讨论无向联通图全局最小割 方法一  因为两点的最小割其实就是最大流,所以我们可以用dinic算法,枚举源点与汇点, 枚举时间复杂度O(n^2) , Dinic算法 时间复杂度O(n^2m),总的时间复杂度O(N^4M),显然当n很大的时候,需要的时间特别大, 方法二  Toer-Wagner算法,这个算法的正确性此处不证明,.核心的思想就是借鉴Prim算法,扩展最大生成树,记录

  • 多校15场WHU Harry Potter and the Forbidden Forest(求网络的最小割的最小边数)

    哈利波特想阻止在0点得食尸鬼到达n-1点,于是要破坏几条路,每条路消耗一定魔法,他想知道在耗费最少魔法的情况下,破坏的路最少. (错误思路)比赛时想用费用流来解,对于原边每条边的cost赋值为1,流过之后最小的费用就是最小割得割数,但是运行之后发现结果不然,原因是费用是对于当前流所过边的所有费用而言,并不是割边的费用... 正确解法: (定理? (题解报告就这么给的构图方法,应该是利用了最小割的一些性质))在网络中任意流f是最大流,则该网络的所有可能存在的最小割的边一定包含在该流f的某些满流的边

Tags: