为什么re了。。。

P3366 【模板】最小生成树

雪夜yukiyo @ 2021-11-29 18:51:23

#include<bits/stdc++.h>
using namespace std;
int n,m,fa[1000010],ans,road;
struct node{
    int x,y,p;
}tree[1000010];
bool cmp(node x,node y)
{
    return x.p<y.p;
}
int find(int x)
{
    if(fa[x]==x) return x;
    else find(fa[x]);
}
void Union(int x,int y)
{
    fa[find(x)]=find(y);
}
void kruskal()
{
    sort(tree,tree+m+1,cmp);
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;road<n-1;i++)
    {
        if(find(tree[i].x)!=find(tree[i].y))
        {
            Union(tree[i].x,tree[i].y);
            road++;
            ans=ans+tree[i].p;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>tree[i].x>>tree[i].y>>tree[i].p;
    }
    kruskal();
    cout<<ans;
    return 0;
}

by SarahAnberlin @ 2021-11-29 19:06:11

如果不连通输出Orz?


by LeTu_Jun @ 2021-11-29 19:07:00

数组开小了


by 雪夜yukiyo @ 2021-12-01 17:17:34

@和国家干部 10e6还小吗 题目的数据范围是10e5啊


by 雪夜yukiyo @ 2021-12-01 17:19:00

@SarahAnberlin 看了一下最后一个测试点确实是 草 我加判定试试


|