5 8
0 1 1
0 2 2
0 3 5
0 4 7
1 2 0
2 3 15
2 4 25
1 4 100
13
#include<bits/stdc++.h> using namespace std; typedef long long ll; inline int read() { int x=0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘)ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x; } const int maxn=1e6+100; int pre[maxn],n,m; struct node{ ll u,v,w; }a[maxn]; bool cmp(node x,node y){ return x.w<y.w; } void inint(){ for(int i=0;i<=n;i++){ pre[i]=i; } } int find(int h)//找根? { return pre[h]==h?h:pre[h]=find(pre[h]); } int merge(node n){ int x=find(n.u); int y=find(n.v); if(x!=y){ pre[x]=y; return 1; } return 0; } int main(){ cin>>n>>m; inint(); for(int i=1;i<=m;i++){ a[i].u=read(); a[i].v=read(); a[i].w=read(); } sort(a+1,a+m+1,cmp); ll num=0,ans=0; for(int i=1;i<=m&&num<=n-1;i++) { if(merge(a[i])==1) { num++; ans+=a[i].w; } } printf("%lld\n",ans); }
https://www.cnblogs.com/SeanOcean/p/10975694.html#autoid-0-0-0
原文:https://www.cnblogs.com/lipu123/p/13302165.html