算法基于这样一个定理:对于任意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)
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 505
#define INF 1000000000
using namespace std;
int map[MAXN][MAXN];
int v[MAXN], dis[MAXN]; //v数组是马甲数组,dis数组用来表示该点与A集合中所有点之间的边的长度之和
bool vis[MAXN];//用来标记是否该点加入了A集合
int Stoer_Wagner(int n)
{
int i, j, res = INF;
for(i = 0; i < n; i ++)
v[i] = i; //初始马甲为自己
while(n > 1)
{
int k, pre = 0; //pre用来表示之前加入A集合的点,我们每次都以0点为第一个加入A集合的点
memset(vis, 0, sizeof(vis));
memset(dis, 0, sizeof(dis));
for(i = 1; i < n; i ++)
{
k = -1;
for(j = 1; j < n; j ++) //根据之前加入的点,要更新dis数组,并找到最大的dis
if(!vis[v[j]])
{
dis[v[j]] += map[v[pre]][v[j]];
if(k == -1 || dis[v[k]] < dis[v[j]])
k = j;
}
vis[v[k]] = true;//标记该点已经加入A集合
if(i == n - 1) //最后一次加入的点就要更新答案了
{
res = min(res, dis[v[k]]);
for(j = 0; j < n; j ++) //将该点合并到pre上,相应的边权就要合并
{
map[v[pre]][v[j]] += map[v[j]][v[k]];
map[v[j]][v[pre]] += map[v[j]][v[k]];
}
v[k] = v[-- n];//删除最后一个点
}
pre = k;
}
}
return res;
}
int main(){
int n, m, u, v, w;
while(scanf("%d%d", &n, &m) != EOF)
{
memset(map, 0, sizeof(map));
while(m --)
{
scanf("%d%d%d", &u, &v, &w);
map[u][v] += w;
map[v][u] += w;
}
printf("%d\n", Stoer_Wagner(n));
}
return 0;
}
分享到:
相关推荐
北大POJ2516-Minimum Cost 解题报告+AC代码 http://blog.csdn.net/lyy289065406/article/details/6742534
关于在最小割推荐题目中的源码(包括poj,Hdu两大题库的题目)
poj2516代码最小费用最大流
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
NULL 博文链接:https://128kj.iteye.com/blog/1705139
NULL 博文链接:https://200830740306.iteye.com/blog/603493
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等