poj 2914 Minimum Cut（全局最小割）

题目大意：给你一个无相图，求出一个最小的割，使得原图不连通。

明显的全局最小割的裸题，用到了一个叫做SW算法的东西

就是每次在图中找到一个割s-t,C，然后用C去更新答案，然后在图中把s,t两个点合并，当最后图只有一个点时就可以了

证明也没看懂

#include<cstdio>
#include<cstring>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=511,inf=~0u>>2;
int n,m; int map[maxn][maxn];
void init(){
memset(map,0,sizeof(map)); int a,b,c;
for (int i=1;i<=m;++i) scanf("%d%d%d",&a,&b,&c),map[a][b]+=c,map[b][a]+=c;
}
bool can[maxn],vis[maxn]; int dis[maxn],s,t,mincut;
void prim(){
memset(can,1,sizeof(can)); memset(dis,0,sizeof(dis));
s=-1,t=-1; int tmp;
while (1){
int maxx=-inf;
for (int i=0;i<n;++i) if (can[i] && !vis[i] && dis[i]>maxx){
tmp=i; maxx=dis[i];
}
if (t==tmp) return;
s=t; t=tmp; mincut=dis[t]; can[t]=0;
for (int i=0;i<n;++i) if (can[i] && !vis[i]) dis[i]+=map[t][i];
}
}
void work(){
int ans=inf; memset(vis,0,sizeof(vis));
for (int i=1;i<n;++i){
prim(); if (mincut<ans) ans=mincut;
if (!ans) break; vis[t]=1;
for (int j=0;j<n;++j){
map[s][j]+=map[t][j];
map[j][s]+=map[j][t];
}
}
printf("%d\n",ans);
}
int main(){
while (scanf("%d%d",&n,&m)!=EOF) init(),work();
return 0;
}