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 GGapa @ 2023-07-12 15:58:21

我去下载了一个样例来看,自测发现并没有问题:

input
5 18
2 4 276
3 3 435
3 4 608
2 4 860
1 2 318
1 3 547
5 4 419
2 5 98
1 5 460
5 3 399
3 5 240
3 2 733
3 3 903
4 2 909
5 2 206
3 4 810
2 1 115
2 3 419
output:
729

测试记录


by GGapa @ 2023-07-12 16:01:27

@GGapa 是测试点1


by FTR_CLCX @ 2023-07-12 16:03:10

@GGapa 你洛谷在线IDE试试


by FTR_CLCX @ 2023-07-12 16:03:48

@GGapa 本地和洛谷评测机输出有可能不同


by 六楼溜刘 @ 2023-07-12 16:04:06

@GGapa 快读写错了


by 六楼溜刘 @ 2023-07-12 16:04:20

@GGapa 看看我的


by 六楼溜刘 @ 2023-07-12 16:04:45

#define gc getchar()
inline int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc

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

你把空字符(比如换行 \n)当数字读了,但 Windows 默认忽略空字符,Linux 不会忽略


by 六楼溜刘 @ 2023-07-12 16:08:33

所以你本地没问题传上去有问题


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

@六楼溜刘 别人大括号要还行,不如我的

inline int rd()
{
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    return x*f;
}

| 下一页