hsy20101122 @ 2024-02-19 22:35:09
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[200001],ans;
struct edge{
int u,v,w;
}e[200001];
bool cmp(edge a,edge b){
return a.w<b.w;
}
int getfather(int x){
if(x==fa[x]){
return x;
}
return fa[x]=getfather(fa[x]);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
sort(e+1,e+1+m,cmp);
for(int i=1;i<=m;i++){
int eu=getfather(e[i].u);
int ev=getfather(e[i].v);
if(eu==ev){
continue;
}
fa[eu]=ev;
ans+=e[i].w;
}
if(ans>0){
cout<<ans;
}else{
cout<<"orz";
}
return 0;
}```
by gotocspandbetter @ 2024-02-19 22:47:44
将判断输出orz的条件改为最小生成树的边数是否等于节点数减1,是输出ans,不是输出orz
by gotocspandbetter @ 2024-02-19 22:48:07
@huangshuyuan2010
by gotocspandbetter @ 2024-02-19 22:51:29
一张图要连通,则至少需要n-1条边
by hsy20101122 @ 2024-02-20 13:39:20
@gotocspandbetter 谢谢大神