测试点13 一直过不去,为啥,求助

P3366 【模板】最小生成树

Duanshuangli @ 2024-08-18 09:32:45


#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int n,m,res=0,cnt=0;
int f[N];
struct node
{
    int x,y,z;
}e[2*N];
bool cmp(node a,node b)
{
    return a.z<b.z;
}
void init()
{
    for(int i=1;i<=N;i++)
        f[i]=i;
}
int find(int x)
{
    if(f[x]==x)
        return x;
    else
        return f[x]=find(f[x]);
}
void klskr()
{
    for(int i=1;i<=m;i++)
    {
        int fx=find(e[i].x);
        int fy=find(e[i].y);
        if(fx!=fy)
        {
            res+=e[i].z;
            f[fx]=fy;
            cnt++;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    init();
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[i]={u,v,w};
    }
    sort(e+1,e+m+1,cmp);
    klskr();
    if(cnt<n-1)
    {
        cout<<"orz";
        return 0;
    }
    cout<<res;
    return 0;
}

by Duanshuangli @ 2024-08-18 10:54:49

@Duanshuangli 我本人来回复一下吧,就是在初始化的时候,在init()函数里面,把i<=N,改成i<=n,即可


by gaohongyuan @ 2024-09-15 12:18:11

看不懂


|