C++只过了最后一个点,蒟蒻求调

P3366 【模板】最小生成树

GGapa @ 2023-07-12 15:56:12

//P3366 【模板】最小生成树

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

const int maxn=2e5+5;

int n,m;

struct EDGE//dui
{
    int left,right;
    int value;
};

EDGE edge[maxn];
int father[maxn];
int succeed=0,ans=0;

 int read()//right
{
    int f=1,x=0;
    char c;
    c=getchar();
    if(c=='-')f=-1,c=getchar();
    while('0'<=c&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

 bool cmp(EDGE x,EDGE y) //right
{
    return x.value<y.value;
}

 int find(int it)//right
{
    if(it==father[it])return it;
    else return father[it]=find(father[it]);
}

int main()
{
    n=read(),m=read();
    for(int i = 1;i<=n;i++)father[i]=i;
    for(int i = 1;i<=m;i++)
    {
        edge[i].left=read();
        edge[i].right=read();
        edge[i].value=read();
    }
    sort(edge+1,edge+1+m,cmp);
    for(int i = 1;i<=m;i++)
    {
        int findl=find(edge[i].left),findr=find(edge[i].right);
        if(findl!=findr)
        {
        father[findr]=findl;
        succeed++;ans+=edge[i].value;
        }
        if(succeed>=n-1)
        {
            cout<<ans<<endl;
            return 0;
        }
    }
    printf("orz\n");
    return 0;
}

by 六楼溜刘 @ 2023-07-12 16:22:56

@spider_oyster 感觉不如这个

int read(){
    int x;cin>>x;return x;
}

by spider_oyster @ 2023-07-12 16:24:08

@六楼溜刘 为什么不是:

inline rd()
{
    ...
}

by 六楼溜刘 @ 2023-07-12 16:25:47

@spider_oyster @GMJoanna 这个b去年CSPS全这样写的直接爆0了


by GGapa @ 2023-07-12 22:13:26

谢谢各位神犇,问题解决了


上一页 |