第一次写kruskal,求助
查看原帖
第一次写kruskal,求助
1283045
NOI109_bjh楼主2024/9/15 11:55

查不出问题,求助大佬,只过了最后一个测试点。。。

#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
}
2024/9/15 11:55
加载中...