Tang-Dreamoon's Blog

poj 2914 最小割集

发表于 | 分类于 ， ，

一个不是网络流的最小割（stoer_wagner算法）

　　题目链接：poj 2914

　　题意：给定一个带权的无向图，求割掉最少权值的边，使图不连通。（即带权边连通度）

　　题解：比较暴力的做法是固定一个源点，然后枚举所有的汇点求最小割，找其中最小的一个，就是整个图的边连通度。可是这个复杂度显然是（N ^ 3 * M）的——碰巧这个题过不去，⊙﹏⊙汗。所以我们只能用牛逼的鸡肋算法 stoer_wagner ，讲道理本人并不是特别明白这个算法的原理和正确性，而且相信我，全百度没有一个人会的。在此转载一个个人感觉将算法步骤解释的比较清楚的博客：大佬的博客。

　　我思故我在：人生中第一个没有理解就背过了的模板。烦……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int map[505][505],w[505],v[505];
bool vis[505];
int min(int a,int b)
{
	return a < b ? a : b;
}
int work()
{
	int mina=2147483647;
	for(int i=0;i<n;i++)
		v[i]=i;
	while(n>1)
	{
		int last=0;
		memset(vis,0,sizeof(vis));
		memset(w,0,sizeof(w));
		for(int i=1;i<n;i++)
		{
			int k=-1;
			for(int j=1;j<n;j++)
			{
				if(!vis[v[j]])
				{
					w[v[j]]+=map[v[last]][v[j]];
					if(k==-1||w[v[j]]>w[v[k]])
						k=j;
				}
			}
			vis[v[k]]=1;
			if(i==n-1)
			{
				mina=min(mina,w[v[k]]);
				for(int j=0;j<n;j++)
				{
					map[v[last]][v[j]]+=map[v[j]][v[k]];
					map[v[j]][v[last]]+=map[v[j]][v[k]];
				}
				v[k]=v[--n];
			}
			last=k;
		}
	}
	return mina;
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(map,0,sizeof(map));
		for(int i=1;i<=m;i++)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			map[x][y]+=z;
			map[y][x]+=z; 
		}
		printf("%d\n",work());
	}
	return 0;
}