POJ 2914 题意：给定一个无向图 小于500节点，和边的权值，求最小的代价将图拆为两个联通分量。
Stoer Wagner算法：
（1）用类似prim算法的方法求“最大生成树”，但是它比较的权值为w(A,x)A为所有在树上的点，x不在树上。
（2）剩下最后一个节点等待加入树的时候，用W（A，xn）更新ans ，并且将最后一个节点和倒数第二个节点合并。
（3）运行N-1次“最大生成树”，就得到了答案
补充几点：（1）像这种数据规模比较小的题目，没必要用优先队列或者堆优化，反而会超时。。
（2）这道题用流输入输出会超时。。。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> using namespace std; typedef long long int LL; const int maxn=500,maxm=maxn*maxn/2; int w[maxn][maxn],dist[maxn],m,n,point[maxn]; bool intree[maxn]; int po(int x) { if(x==point[x])return x; else return point[x]=po(point[x]); } void combine(int a,int b) { a=po(a);b=po(b); bool counted[maxn];memset(counted,0,sizeof(counted)); for(int i=0;i<n;i++) { int np=po(i); if((np==a)||(np==b)||(counted[np]))continue; counted[np]=true; w[np][a]+=w[np][b];w[a][np]+=w[b][np]; } point[b]=a; } int main() { ios::sync_with_stdio(false); while(scanf("%d%d",&n,&m)!=EOF) { memset(w,0,sizeof(w)); int a,b,c; for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); w[a][b]+=c;w[b][a]+=c; } for(int i=0;i<n;i++) point[i]=i; int ans=1e+9; for(int ii=1;ii<n;ii++) { if(ans==0)break; memset(dist,0,sizeof(dist));memset(intree,0,sizeof(intree)); int pre=po(0),sum=1; intree[pre]=true; while(sum<=(n-ii)) { int maxk=-1; bool counted[maxn];memset(counted,0,sizeof(counted)); for(int i=0;i<n;i++) { int np=po(i); if((intree[np])||(counted[np]))continue; counted[np]=true; dist[np]+=w[pre][np]; if((maxk==-1)||(dist[np]>dist[maxk])) { maxk=np; } } if(maxk==-1){ans=0;break;} intree[maxk]=true; if(sum==(n-ii)) { combine(pre,maxk); ans=min(ans,dist[maxk]); } pre=maxk; sum++; } } printf("%d ",ans); } return 0; }