[无向图全局最小割]zoj 2753：Min Cut (Destroy Trade Net)

大致题意：
    给出一个无向图，求移除权值最少的边使得这个图被分为两个连通块。

 

大致思路：

    裸的StoerWagner模版题，在神牛的博客瞎逛的时候看到了，就刷掉吧……希望不要降RP

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax = 505;
const int inf = 1<<30;

int map[nMax][nMax];
int v[nMax], dis[nMax];
bool vis[nMax];

int StoerWagner(int n){   //点数从0开始
    int i,j,res=inf;
    for(i=0;i<n;i++)
        v[i]=i;
    while(n>1){
        int k=1,pre=0;
        for(i=1;i<n;i++){
            dis[v[i]]=map[v[0]][v[i]];
            if(dis[v[i]]>dis[v[k]])
                k=i;
        }
        memset(vis,0,sizeof(vis));
        vis[v[0]]=true;
        for(i=1;i<n;i++){
            if(i==n-1){
                res=min(res,dis[v[k]]);
                for(j=0;j<n;j++){
                    map[v[pre]][v[j]] += map[v[j]][v[k]];
                    map[v[j]][v[pre]] += map[v[j]][v[k]];
                }
                v[k] = v[-- n];
            }
            vis[v[k]] = true;
            pre = k;
            k = -1;
            for(j = 1; j < n; j ++)
                if(!vis[v[j]]){
                    dis[v[j]] += map[v[pre]][v[j]];
                    if(k == -1 || dis[v[k]] < dis[v[j]])
                        k = j;
                }
        }
    }
    return res;
}

int main(){
    int n,m,u,v,w,s;
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(map,0,sizeof(map));
        while(m--){
            scanf("%d%d%d",&u,&v,&w);
            //u--;v--;
            map[u][v]+=w;
            map[v][u]+=w;
        }
        printf("%d\n",StoerWagner(n));
    }
    return 0;
}