Kruskal模板

///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> using namespace std; const int MAXN=505;//最大点数 const int 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]); } //传入点数，返回最小生成树的权值，如果不连通返回-1 int 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("%d\n",ans); else printf("?\n"); } return 0; }