奇怪的事情

P3366 【模板】最小生成树

lcc_cc @ 2022-08-31 22:14:00

#include<bits/stdc++.h>
using namespace std;
struct node{
    int h,t,w;
}a[5005];
int fa[5005],cnt,n,ans,m;
int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
bool cmp(node x,node y){
    return x.w<y.w;
}
void inti(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++) cin>>a[i].h>>a[i].t>>a[i].w;
    return;
}
void dj(){
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++){
        int x=a[i].h,y=a[i].t,z=a[i].w;
        int fx=find(x),fy=find(y);
        if(fx==fy) continue;
        fa[fx]=fy;
        ans+=z;
        cnt++;
    }
    if(cnt==n-1) cout<<ans;
    else cout<<"orz";
    return;
}
int main(){
    inti();
    dj();
    return 0;
}

by lcc_cc @ 2022-08-31 22:14:54

为什么这份代码会MLE?不应该RE吗?


by lcc_cc @ 2022-08-31 22:15:28

记录


by songtj @ 2022-09-20 17:40:59

@lcc_cc 您都开完隐了,发评测记录有意义吗?


by zsyzsy_2012 @ 2022-09-27 15:13:30

@lcc_cc 还有,您的并查集合并是不是有问题呀

不只是合并当前,应该把这个节点的“阵营”的父亲设为另一个吧


by lcc_cc @ 2022-09-29 23:24:52

@ZhaoShanYang 有没有一种可能,我用了路径压缩


by zsyzsy_2012 @ 2022-09-30 07:26:45

@lcc_cc 这个题不用压缩,普通Kruskal并查集完全可以A


by lcc_cc @ 2022-09-30 20:29:06

@ZhaoShanYang 为什么要和复杂度过不去,也就一行的事


|