求助:本人代码为何厌氧

P3366 【模板】最小生成树

Pacyd5 @ 2024-07-01 21:05:59

RT.本人代码不开O2就能AC,但开了O2就WA on #8,9,10

#include<bits/stdc++.h>
using namespace std;
const int N=5000,M=400010;
struct sd
{
    int fr,to,w;
}E[M];
int n,m,ans,s,f[N];
bool cmp(sd a,sd b)
{
    return a.w<b.w;
}
int find(int p)
{
    if (p==f[p])
        return p;
    return f[p]=find(f[p]);
}
void kruskal()
{
    for(int i=1;i<=m;i++)
    {
        int u=E[i].fr,v=E[i].to;
        u=find(u);
        v=find(v);
        if (u!=v)
        {
            f[u]=v;
            ans+=E[i].w;
            s++;
        }
        if (s+1==n)
            return;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++)
        cin>>E[i].fr>>E[i].to>>E[i].w;
    sort(E+1,E+m+1,cmp);
    kruskal();
    if (s+1!=n)
        cout<<"orz"<<endl;
    else
        cout<<ans<<endl;
}

by King_and_Grey @ 2024-07-01 21:08:10

@Pacyd5 P1928 外星密码这题一吸氧就 RE,不吸氧就AC

和你的情况差不多(但我也不知道为什么)


by ATZdhjeb @ 2024-07-01 21:09:10


by Pacyd5 @ 2024-07-01 21:13:33

@ATZdhjeb thk.此贴结


|