#include <bits/stdc++.h> using namespace std ; const int N=5003,M=2e5+2; int f[N],n,m; struct E{ int x,y,z; }e[M]; int find(int x){ return x==f[x]?x:f[x]=find(f[x]); } int cmp(E x,E y){ return x.z<y.z; } void krus(){ sort(e+1,e+1+m,cmp); int i,x,y,fx,fy,z,c=0,s=0; for(i=1;i<=n;i++) f[i]=i; for(i=1;i<=m;i++){ x=e[i].x,y=e[i].y,fx=find(x),fy=find(y); if(fx!=fy){ f[fx]=fy; c++,s+=e[i].z; if(c==n-1) break; } } cout<<s<<endl; } signed main(){ int i,x,y,z; cin>>n>>m; for(i=1;i<=m;i++) cin>>e[i].x>>e[i].y>>e[i].z; krus(); }
标签:return,int,最小,生成,板子,find From: https://www.cnblogs.com/towboa/p/17203040.html