zzxzzxCCC @ 2023-08-15 20:35:49
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
struct rec{
int x,y,z;
}edge[500010];
bool operator <(rec a,rec b){
return a.z<b.z;
}
int fa[100010],n,m;
int getfa(int x){
if(x==fa[x]) return x;
return fa[x]=getfa(fa[x]);
}
int main(){
int ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
for(int i=1;i<=n;i++) fa[i]=i;
sort(edge+1,edge+m+1);
for(int i=1;i<=m;i++){
int x=getfa(edge[i].x),y=getfa(edge[i].y);
if(x==y) continue;
fa[x]=y;
ans+=edge[i].z;
}
if(ans==0) { printf("orz");return 0;}
printf("%d",ans);
return 0;
}
by yqr123YQR @ 2023-08-15 20:39:03
ans = 0 不一定说明不连通啊
by yqr123YQR @ 2023-08-15 20:39:58
应该直接循环统计最后剩下了几个连通块
by 蒟蒻的我orz @ 2023-08-22 17:01:59
int cnt=0;
for(int i=1;i<=m;i++){
int x=getfa(edge[i].x),y=getfa(edge[i].y);
if(x==y) continue;
fa[x]=y;
ans+=edge[i].z;
cnt++;
if(cnt==n-1)break;
}
if(cnt!=n-1) { printf("orz");return 0;}
printf("%d",ans);