POJ PKU 2914 无向图最小割 StoerWagner_JosiahChiu

http://blog.sina.com.cn/u/1684496212

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

POJ PKU 2914 无向图最小割 StoerWagner

(2010-08-02 15:48:06)

标签：

poj

pku

2914

最小割

stoerwagner

it

分类：网络流

题目描述：

给你无向图的信息（点和边的容量），求最小割。

解题报告：

朴素的最大流算法，由于源点和汇点是要固定的，所以固定了源点后，要枚举汇点
所以复杂度是O(n^4)以上。
而利StoerWagner用类似prim的算法（最大生成树）。
复杂度O(n^3), 如果加了堆优化，复杂度O(n^2logn)。
算法过程如下：
1. 设最小割cut=INF, 任选一个点s到集合A中, 定义W(A, p)为A中的所有点到A外一点p的权总和.
2. 对刚才选定的s, 更新W(A,p)(该值递增).
3. 选出A外一点p, 且W(A,p)最大的作为新的s, 若A!=G(V), 则继续2.
4. 把最后进入A的两点记为s和t, 用W(A,t)更新cut.
5. 新建顶点u, 边权w(u, v)=w(s, v)+w(t, v), 删除顶点s和t, 以及与它们相连的边.
6. 若|V|!=1则继续1.

代码如下：

#include<iostream>
using namespace std;
#define size 600
int n, m, g[size][size];
int A[size], w[size], vst[size];
int StoerWagner(int n)
{
    A[0] = 0; int ans = 0x7fffffff, cnt = 0;
    memset(vst, 0, sizeof(vst));
    for(int i = 1; i < n; i++)
    {
        vst[A[0]] = 1; cnt = 1;
        for(int j = 0; j < n; j++) if (!vst[j]) w[j] = g[A[0]][j];
        while(true)
        {
            int id = -1;
            for(int j = 0; j < n; j++)
                if (!vst[j] && (id == -1 || w[j] > w[id]))
                    id = j;
            if (id == -1) break;
            vst[id] = 1; A[cnt++] = id;
            for(int j = 0; j < n; j++)
                if (!vst[j]) w[j] += g[id][j];
        }
        if (cnt >= 2)
        {
            int s1 = A[cnt - 2], s2 = A[cnt - 1];
            if (w[s2] < ans) ans = w[s2];
            vst[s2] = 2;
            for(int j = 0; j < n; j++)
                if (vst[j] != 2)
                {
                    vst[j] = 0;
                    g[s1][j] = g[j][s1] = g[s1][j] + g[s2][j];
                }
            g[s1][s2] = 0;
        }
    }
    return ans;
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(g, 0, sizeof(g));
        for(int i = 0; i < m; i++)
        {
            int a, b, c;scanf("%d%d%d", &a, &b, &c);
            g[a][b] += c; g[b][a] += c;
        }
        printf("%d\n", StoerWagner(n));
    }
    return 0;
}

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：POJ 2-SAT 六道题目总结

后一篇：POJ PKU 1422 最小路径覆盖。

新浪BLOG意见反馈留言板　欢迎批评指正