一片黑,MLE

P3366 【模板】最小生成树

chenhao_li @ 2024-12-15 14:57:21

全部MLE,求解

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

int n,m,k,ans;//k is mst edges,ans
struct edge{
    int u,v,w;
};
edge e[200010];
int fa[5010];
bool cmp(edge a,edge b){
    return a.w>b.w;
}

int Find(int x){
    if(fa[x]==x) return x;
    else return fa[x]=Find(x);
}
void Union(int x,int y){
    int fx=Find(x);
    int fy=Find(y);
    if(fx!=fy) fa[fy]=fx;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=1;//每个顶点自成联通分量
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+1+m,cmp);
    //kruskal算法
    for(int i=1;i<=m;i++){
        if(Find(e[i].u)!=Find(e[i].v)){//边的两端不是一个联通分量
            k++;
            ans+=e[i].w;
            Union(e[i].u,e[i].v);
            if(k==n-1) break;
        }
    }
    if(k!=n-1) cout<<"orz"<<endl;
    else cout<<ans<<endl;
    return 0;
}

by __yun__ @ 2024-12-15 14:59:41

@chenhao_li

for(int i=1;i<=n;i++) fa[i]=1;//每个顶点自成联通分量

改成

for(int i=1;i<=n;i++)fa[i]=i;

by __yun__ @ 2024-12-15 15:01:21

bool cmp(edge a,edge b){
    return a.w>b.w;
}

改成

bool cmp(edge a,edge b){
    return a.w<b.w;
}

by __yun__ @ 2024-12-15 15:05:17

else return fa[x]=Find(x);

改成

else return fa[x]=Find(fa[x]);

by chenhao_li @ 2024-12-15 15:33:15

@yun 谢谢高人指点


|