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:31:38

@IDNo1 不知道,毒氧(?)


by IDNo1 @ 2023-10-16 21:32:51

@Misty_Hazers 已关偶(不知道支持不支持回qwq)


by Misty7 @ 2023-10-16 21:33:09

@IDNo1 不支持qwq


by IDNo1 @ 2023-10-16 21:34:01

@Misty_Hazers o,没四


by bhbffm35429 @ 2024-01-08 22:03:00

@IDNo1 find()和_union()不应有返回值


上一页 |