66分求助

P3366 【模板】最小生成树

Hiscraft @ 2023-08-19 15:43:30

#include<bits/stdc++.h>
using namespace std;
struct node{
    int u,v,l;
}a[114514];
int n,m,ans,f[11451];
bool cmp(node a,node b)
{
    return a.l<b.l;
}
int q(int x){
    if(f[x]==x) return x;
    else return f[x]=q(f[x]);
}
//Kruskal 算法
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++) cin>>a[i].u>>a[i].v>>a[i].l;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m&&n>1;i++){
        if(q(a[i].u)==q(a[i].v)) continue;
        f[q(a[i].u)]=q(a[i].v);
        ans+=a[i].l;
    }
    if(ans) cout<<ans;
    else cout<<"orz";
}

by ruojiyz @ 2023-08-19 15:59:00

@Hiscraft 帮你看了一下,问题有点多:

1.a数组开小了,导致RE,因为边有200000条你只开了100000左右。

2.kruskal是要选n - 1条边,你这里是忘写n--了吧。

3.并不是ans有值就输出,而是n == 1才输出ans,因为n == 1才能说明选出了n - 1条边即图联通,否则图是不连通的,ans有值只能说明你选过边。

代码自己调,加油吧。


|