[无向图全局最小割]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;}