用kruskal86分,还re了1个点,为啥啊各位大佬

P3366 【模板】最小生成树

dream_Hao @ 2022-08-04 13:13:51

#include<bits/stdc++.h>
using namespace std;

struct code{
    long long int a,b;
    long long int d;
};

bool dx(code a,code b){
    return a.d<=b.d;
}

int find(int x,int f[])
{
    if(f[x]==x){
        return x;
    }
    else return find(f[x],f);
}

int main()
{
    long long int n,m,i,s=0,ans=0,x,y;
    cin>>n>>m;
    code a[m];
    int f[n+1];
    for(i=1;i<=n;i++) f[i]=i;
    i=0;
    while(i!=m){
        cin>>a[i].a>>a[i].b>>a[i].d;
        if(a[i].a==a[i].b){
            m--;
            continue;
        }
        i++;
    }
    sort(a,a+m,dx);
    for(i=0;i<m;i++){
        x=find(a[i].a,f);y=find(a[i].b,f);
        if(x==y) continue;
        ans+=a[i].d;s++;
        if(s==n-1) break;
        f[y]=x;
    }
    if(s!=n-1) cout<<"orz";
    else cout<<ans;
    cin>>n;
}

by Infinite_Energy @ 2022-08-04 13:14:39

dx函数=号去掉


by Infinite_Energy @ 2022-08-04 13:15:18

@dream_Hao


by dream_Hao @ 2022-08-04 13:29:03

@x123s456j789 谢谢大佬


by songtj @ 2022-09-20 17:45:02

@dream_Hao sortcmp 函数里的比较是不能写 = 号的,可能会导致排序错误,可以看看OI Wiki

链接

里面明确提到:

进行排序的运算符必须满足严格弱序,否则会出现不可预料的情况(如运行时错误、无法正确排序)。

常见的错误做法:使用 <= 来定义排序中的小于运算符。


|