【模板】最小生成树 发表于 2018-07-21 【模板】最小生成树 Kruskal算法 1234567891011121314151617181920212223242526272829303132//最小生成树_Kruskal #include<cstdio>#include<algorithm>using namespace std;int n,m,f[5005],ans,cnt,fx,fy;struct node { int x,y,z;} a[200005];bool cmp(node x,node y) { return x.z<y.z;}int find(int k) { if(f[k]==k)return k; return f[k]=find(f[k]);}int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++)f[i]=i;//初始化并查集 for(int i=1; i<=m; i++) { scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); } sort(a+1,a+1+m,cmp);//按边权升序排序 for(int i=1; i<=m; i++) { fx=find(a[i].x);fy=find(a[i].y); if(fx==fy)continue;//如果已相连则不再连 f[fy]=fx; ans+=a[i].z; cnt++; if(cnt==n-1)break; } printf("%d",ans);}