题意：
求无向图的全局最小边割。
分析：
stoer-wagner模板。
代码：
//poj 2914
//sep9
#include <iostream>
using namespace std;
const int maxN=512;
int g[maxN][maxN];
int b[maxN],dist[maxN];
int n,m;int Min_Cut_Phase(int ph,int &x,int &y)
{int i,j,t;t=1;b[1]=ph;for(i=1;i<=n;++i)if(b[i]!=ph) dist[i]=g[1][i]; for(i=1;i<n;++i){x=t;for(t=0,j=1;j<=n;++j)if(b[j]!=ph&&(!t||dist[j]>dist[t]))t=j;b[t]=ph;for(j=1;j<=n;++j)if(b[j]!=ph) dist[j]+=g[t][j]; }return y=t,dist[t];
}void Merge(int x,int y)
{int i;if(x>y) swap(x,y);for(i=1;i<=n;++i)if(i!=x&&i!=y)g[i][x]+=g[i][y],g[x][i]+=g[y][i];if(y==n)return ;for(i=1;i<n;++i) if(i!=y){swap(g[i][y],g[i][n]);swap(g[y][i],g[n][i]);}return ;
}int main()
{while(scanf("%d%d",&n,&m)==2){memset(g,0,sizeof(g));while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);++a,++b;g[a][b]+=c;g[b][a]+=c;}int ret=INT_MAX,i,x,y;memset(b,0,sizeof(b));for(i=1;n>1;++i,--n){ret=min(ret,Min_Cut_Phase(i,x,y));Merge(x,y); }printf("%d\n",ret);}return 0;
}