求助!!!!72分,四个RE!

P3366 【模板】最小生成树

mljyhp_zzx @ 2023-04-15 15:57:15

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int a,b,l;
}v[2000001];
int fa[50001],rak[50001],n,m,sum,cnt;
int find(int x)
{
    if(fa[x]==x)return x;
    else fa[x]=find(fa[x]);
    return fa[x];
}
void Union(int x,int y)
{
    int a1=find(x),b1=find(y);
    if(rak[a1]<=rak[b1])fa[a1]=b1;
    else fa[b1]=a1;
    if(rak[a1]==rak[b1] && a1!=b1)rak[b1]++;
}
void input()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i,rak[i]=1;
    for(int i=1;i<=m;i++)cin>>v[i].a>>v[i].b>>v[i].l;
    return;
}
bool cmp(node x,node y)
{
    return x.l<=y.l;
}
int main()
{
    input();
    sort(v+1,m+v+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(find(v[i].a)!=find(v[i].b))
        {
            Union(v[i].a,v[i].b);
            sum+=v[i].l;
            cnt++;
        }
        if(cnt==n-1)break;
    }
    if(cnt!=n-1)
    {
        cout<<"orz"<<endl;
        return 0;
    }
    cout<<sum;
    return 0;
}

by mljyhp_zzx @ 2023-04-15 16:01:17

求助!!!!72分,四个RE!


by beside_the_pavilion @ 2023-04-15 16:22:40

数组开的不够大?


by Fischl322 @ 2023-05-03 22:40:47

看数据范围,数组开小了


by mljyhp_zzx @ 2023-06-03 15:18:20

谢谢


|