第一次写kruskal，求助

NOI109_bjh @ 2024-09-15 11:55:46

#include<bits/stdc++.h>
#define int long long
#define ci const int
#define elif else if

using namespace std;

ci E=2e5+10,e=5010;
int n,m,f[e],cou=1,ans;

struct edge{
    int x,y,e;
}t[E];

bool cmp(edge x,edge y){
    return x.e<y.e;
}

int get(int x){
    return x==f[x]?x:f[x]=get(f[x]);
}

void kru(){
    sort(t+1,t+1+m,cmp);

    for(int i=1;i<=m;i++){
        if(get(t[i].x)==get(t[i].y))continue;
        f[t[i].x]=t[i].y,ans+=t[i].e,cou++;
        if(cou==n)break;
    }

    if(cou==n-1)cout<<ans;
    else cout<<"orz";

    return;
}

signed main(){
    ios::sync_with_stdio(0),
    cin.tie(0),cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++)f[n]=i;
    for(int i=1;i<=m;i++)cin>>t[i].x>>t[i].y>>t[i].e;
    kru();

    return 0;//保AC
}

by csxx601cjy @ 2024-09-15 12:01:08

#include<bits/stdc++.h>
using namespace std;
int Set[10001],n,m,k,cnt=0,sum=0;
int Find(int x){
    Set[x]=x!=Set[x]?Find(Set[x]):Set[x];
    return Set[x];
}
void merge(int a,int b){
    if(Find(a)!=Find(b))Set[Find(a)]=Find(b);
}
struct node{
    int x,y,z;
}a[200001];
bool cmp(node a,node b){
    return a.z<b.z;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++)cin>>a[i].x>>a[i].y>>a[i].z;
    for(int i=0;i<=n;i++)Set[i]=i;
    sort(a,a+m,cmp);
    for(int i=0;i<m;i++){
        if(Find(a[i].x)!=Find(a[i].y)){
            merge(a[i].x,a[i].y);
            cnt++;
            sum+=a[i].z;
        }
    }
    if(cnt<n-1)cout<<"orz";
    else cout<<sum;
    return 0;
}

by zhangzirui66 @ 2024-09-15 12:08:31

@NOI109_bjh cou没++

by kevinZ99 @ 2024-09-15 12:18:12

@NOI109_bjh

1、并查集初始化的时候写错了 f[n]=i -> f[i]=i

2、选边合并的时候并不是

f[t[i].x]=t[i].y

而是

f[get(t[i].x)]=get(t[i].y)

因为是将 t[i].x 所在的集合所有的点合并到 t[i].y 的集合。

3、你的 cou 的初始值是 1 所以你输出的时候并不是

if(cou==n-1)

而是

if(cou==n)

因为最小生成树有 n-1 条边，但是由于你的初始值是 1 即 1+n-1=n 所以应该判断 n

by NOI109_bjh @ 2024-09-15 13:16:19

@kevinZ99 谢谢大佬！