Lance1_1 @ 2023-10-26 13:37:49
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=200005;
int cnt,res=0,num=0;
int fa[5005];
struct edge{
int to,next,val;
}e[maxn];
int n,m;
bool cmp(edge a,edge b){
return a.val<b.val;
}
void iint(int n){
for(int i=1;i<=n;i++){
fa[i]=i;
}
}
int find(int k){
if(fa[k]==k)return k;
else return fa[k]=find(fa[k]);
}
void Union(int x,int y){
x=find(x);
y=find(y);
if(x!=y) fa[y]=x;
}
bool check(int x,int y){
if(fa[x]==fa[y]) return true;
else return false;
}
int main(){
cin>>n>>m;
iint(n);
for(int i=1;i<=m;i++){
cin>>e[i].to>>e[i].next>>e[i].val;
}
sort(e+1,e+m+1,cmp);
cnt=0;
for(int i=1;i<=m;i++){
if(cnt==n-1) break;
if(check(e[i].to,e[i].next)==false){
Union(e[i].to,e[i].next);
res+=e[i].val;
cnt++;
}
}
if(cnt==n-1){
cout<<res<<endl;
}
else{
cout<<"orz"<<endl;
}
return 0;
}
by Missdie @ 2023-10-26 14:20:29
for (int i = 1; i <= m; i ++){
int qx = que(e[i].u);
int qy = que(e[i].v);
if (qx == qy) continue;
fa[qx] = qy;
cnt ++, sum += e[i].w;
}
if (cnt < n) puts("orz");
else printf("%lld", sum);
这样子会舒服一点
by cy1999_de_dog @ 2023-10-26 14:35:52
check函数写错了
找两个点的祖先是否相同,而非他们父亲
by Lance1_1 @ 2023-10-26 16:04:25
@cy1999_de_dog 谢谢您!通过了!
by Lance1_1 @ 2023-10-26 16:05:05
@Missdie 好的,谢谢您!