114514年没打版子全RE求助

P3366 【模板】最小生成树

IDNo1 @ 2023-10-16 21:24:04

#include<bits/stdc++.h>
#define re register int
const int N=5e4+5;
using namespace std;
int n,m,a,b,c;
inline int read()
{
    re x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}
struct Chtholly_tree//??? 
{
    int u,v,w;  
};
vector<Chtholly_tree> e;
int f[N];
bool cmp(Chtholly_tree a,Chtholly_tree b)
{
    return a.w<=b.w;
}
int u,v,w,ans,cnt;
int find(re k)
{
    if(k==f[k])return k;
    else f[k]=find(f[k]);
}
int fx,fy;
int _union(re x,re y)
{
    fx=find(x);
    fy=find(y);
    if(fx!=fy)
    {
        f[x]=fy;
    }
}
int main()
{
    n=read(),m=read();
    while(m--)
    {
        a=read(),b=read(),c=read();
        e.push_back({a,b,c});
    }
    for(re i=1;i<=n;i++)
    {
        f[i]=i;
    }
    sort(e.begin(),e.end(),cmp);
//  for(re i=0;i<e.size();i++)
//  {
//      cout<<e[i].u<<" "<<e[i].v<<" "<<e[i].w<<"\n"; 
//  }
    for(re i=0;i<e.size();i++)
    {
        u=e[i].u,v=e[i].v,w=e[i].w;
        if(find(u)!=find(v))
        {
            _union(u,v);
            ans+=w;
            cnt++;
        }
        if(cnt==n-1)
        {
            break;
        }
//      cout<<ans<<" "<<cnt<<endl;
    }
    if(cnt==n-1)
    {
        cout<<ans;
    }
    else
    {
        cout<<"orz";
    }
    return 0;
}

yzm:xzrp祭


by Misty7 @ 2023-10-16 21:25:22

bool cmp(Chtholly_tree a,Chtholly_tree b)
{
    return a.w<=b.w;
}

改为

bool cmp(Chtholly_tree a,Chtholly_tree b)
{
    return a.w<b.w;
}

by Misty7 @ 2023-10-16 21:28:31

int _union(re x,re y)
{
    fx=find(x);
    fy=find(y);
    if(fx!=fy)
    {
        f[x]=fy;
    }
}

改为

int _union(re x,re y)
{
    fx=find(x);
    fy=find(y);
    if(fx!=fy)
    {
        f[fx]=fy;
    }
}

AC


by IDNo1 @ 2023-10-16 21:28:31

@Misty_Hazers 还是RE捏


by Misty7 @ 2023-10-16 21:28:43

@IDNo1


by Misty7 @ 2023-10-16 21:29:06

@IDNo1 为什么我没有RE


by IDNo1 @ 2023-10-16 21:29:29

@Misty_Hazers 话说这个要双向建边吗


by Misty7 @ 2023-10-16 21:29:59

@IDNo1 不用


by IDNo1 @ 2023-10-16 21:30:05

@Misty_Hazers 开O2全RE,为啥呀qwq


by Misty7 @ 2023-10-16 21:30:38

@IDNo1 代码实现上没有区别


by IDNo1 @ 2023-10-16 21:30:58

@Misty_Hazers ?


| 下一页