jy20091121 @ 2023-10-11 19:12:25
#include<bits/stdc++.h>
using namespace std;
int fi[213132],n,m,ans,eu,ev;
int cnt =0;
struct re{
int u,v,w;
}p[1233022];
bool cmp(re x,re y){
return x.w<y.w;
}
int find(int x){
while(x!=fi[x]) x=fi[x]=fi[fi[x]];
return x;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) fi[i]=i;
for(int i=1;i<=m;i++){
cin>>p[i].u>>p[i].v >>p[i].w;
}
sort(p+1,p+1+n,cmp);
for(int i=1;i<=m;i++){
eu=find(p[i].u),ev=find(p[i].v);
if(eu==ev){
continue;
}
ans+=p[i].w;
fi[ev]=eu;
if(++cnt==n-1) break;
}
cout<<ans;
}
求DALAO指点
by small_john @ 2023-10-11 19:14:45
@zhangjiayii sort(p+1,p+1+n,cmp);
改成 sort(p+1,p+1+m,cmp);
by jy20091121 @ 2023-10-11 19:23:03
@pyy1 谢谢DALAO