Dowemo
0 0 0 0

///Kruskal求MST#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<vector>#include<string>#include<map>#include<set>#include<queue>#include<deque>#include<list>#include<bitset>#include<algorithm>#include<fstream>#include<cstdlib>usingnamespacestd;constint MAXN=505;//最大点数constint MAXM=250005;//最大边数int fa[MAXN],tot;struct Edge
{
 int from,to,cost;
}e[MAXM];void addege(int u,int v,int w) { e[tot].from=u;e[tot].to=v;e[tot++].cost=w; }bool cmp(Edge x,Edge y) { return x.cost<y.cost; }void init(int n) { for(int i=0;i<=n;i++) fa[i]=i; }int Find(int x) { return fa[x]==x?x:fa[x]=Find(fa[x]); }//传入点数,返回最小生成树的权值,如果不连通返回-1int kruskal(int n)
{
 init(n);
 sort(e,e+tot,cmp);
 int cnt=0;
 int ans=0;
 for(int i=0;i<tot;i++)
 {
 int u=e[i].from,v=e[i].to,w=e[i].cost;
 int fu=Find(u),fv=Find(v);
 if(fu!=fv)
 {
 ans+=w;
 fa[fu]=fv;
 cnt++;
 }
 if(cnt==n-1) break;
 }
 if(cnt<n-1) return -1;
 return ans;
}int main()
{
 int n,m;
 while(scanf("%d%d",&m,&n)!=EOF)
 {
 tot=0;
 if(m==0) break;
 int u,v,w;
 for(int i=1;i<=m;i++)
 {
 scanf("%d%d%d",&u,&v,&w);
 addege(u,v,w);
 }
 int ans=kruskal(n);
 if(ans!=-1) printf("%dn",ans);
 elseprintf("?n");
 }
 return0;
}



Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs