Kruskal模板
#include<bits/stdc++.h> using namespace std; struct Edge { int x,y,len; } edge[500010]; int fa[100010],n,m,ans=0; bool operator <(Edge a,Edge b) { return a.len<b.len; } int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int main() { cin>>n>>m; for(int i=1; i<=m; i++) cin>>edge[i].x>>edge[i].y>>edge[i].len; //按照边权排序 sort(edge+1,edge+m+1); //初始化并查集 for(int i=1; i<=n; i++) fa[i]=i; //求最小生成树 for(int i=1; i<=m; i++) { int x=find(edge[i].x); int y=find(edge[i].y); if(x==y) continue; fa[x]=y; ans+=edge[i].len; } cout<<ans<<endl; return 0; }