求助,三个RE(开O2变TLE),数组开的应该是对的

P3366 【模板】最小生成树

PC114514 @ 2023-07-15 11:04:34

RT


#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int x,y,z;
    friend int operator < (node a,node b){
        return a.z <= b.z;
    }
};
int n,m,fa[5005],x,y,z,cnt=0,sum=0;
node a[400005];
int find(int x){
    if(x==fa[x])
        return x;
    return fa[x]=find(fa[x]);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        fa[i] = i;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        a[i].x = x;
        a[i].y = y;
        a[i].z = z;
    }
    sort(a+1,a+m+1);
    for(int i=1;i<=m;i++){
        if(find(a[i].x)!=find(a[i].y)){
            fa[find(a[i].y)] = find(a[i].x);
            sum += a[i].z;
            cnt++;
            if(cnt==n-1)
                break;
        }
    }
    if(cnt!=n-1)
        cout<<"orz";
    else
        cout<<sum;
    return 0;
}

by OldDriverTree @ 2023-07-15 11:15:06

@PC114514 operator 里改成 a.z<b.z


by PC114514 @ 2023-07-15 11:17:02

@OldDriverTree 感谢,过了


|