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 ?