POJ 2914 Minimum Cut Stoer-Wagner（全局最小割）

点击打开链接

Minimum Cut

Time Limit: 10000MS		Memory Limit: 65536K
Total Submissions: 7053		Accepted: 2965
Case Time Limit: 5000MS

Description

Given an undirected graph, in which two vertices can be connected by multiple edges, what is the size of the minimum cut of the graph? i.e. how many edges must be removed at least to disconnect the graph into two subgraphs?

Input

Input contains multiple test cases. Each test case starts with two integers N and M (2 ≤ N ≤ 500, 0 ≤ M ≤ N × (N − 1) ⁄ 2) in one line, whereN is the number of vertices. Following areM lines, each line containsM integers A, B andC (0 ≤ A, B <N, A ≠ B, C > 0), meaning that there C edges connecting verticesA andB.

Output

There is only one line for each test case, which contains the size of the minimum cut of the graph. If the graph is disconnected, print 0.

Sample Input

Sample Output

2
1
2

Source

Baidu Star 2006 Semifinal
Wang, Ying (Originator)
Chen, Shixi (Test cases)
给一个无向有重边的图，有重边的边权累加起来，求最小割。
算法框架：
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<stdio.h>
#include<string.h>
#define M 507
#define inf 0x3f3f3f
using namespace std;
int n,m,mincut,S,T;
int vis[M],g[M][M],combine[M],wet[M];
void search()
{
    int maxx,pos;
    memset(vis,0,sizeof(vis));
    memset(wet,0,sizeof(wet));
    S=T=-1;
    for(int i=0;i<n;i++)
    {
        maxx=-inf;
        for(int j=0;j<n;j++)
            if(!combine[j]&&!vis[j]&&wet[j]>maxx)
            {
                maxx=wet[j];
                pos=j;
            }
        if(T==pos)return;
        S=T;T=pos;
        mincut=maxx;
        vis[pos]=1;
        for(int j=0;j<n;j++)
            if(!combine[j]&&!vis[j])
                wet[j]+=g[pos][j];
    }

}
int Stoer_Wagner()
{
    int ans=inf;
    for(int i=0;i<n-1;i++)
    {
        search();
        if(mincut<ans)ans=mincut;
        if(ans==0)return 0;
        combine[T]=1;
        for(int j=0;j<n;j++)
            if(!combine[j])
            {
                g[S][j]+=g[T][j];
                g[j][S]+=g[j][T];
            }
    }
    return ans;
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(g,0,sizeof(g));
        memset(combine,0,sizeof(combine));
        int a,b,c;
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            g[a][b]+=c;
            g[b][a]+=c;
        }
        int ans=Stoer_Wagner();
        printf("%d\n",ans);
    }
    return 0;
}

秒客网

POJ 2914 Minimum Cut Stoer-Wagner（全局最小割）

相关文章