mljyhp_zzx @ 2023-04-15 15:57:15
#include<bits/stdc++.h>
using namespace std;
struct node
{
int a,b,l;
}v[2000001];
int fa[50001],rak[50001],n,m,sum,cnt;
int find(int x)
{
if(fa[x]==x)return x;
else fa[x]=find(fa[x]);
return fa[x];
}
void Union(int x,int y)
{
int a1=find(x),b1=find(y);
if(rak[a1]<=rak[b1])fa[a1]=b1;
else fa[b1]=a1;
if(rak[a1]==rak[b1] && a1!=b1)rak[b1]++;
}
void input()
{
cin>>n>>m;
for(int i=1;i<=n;i++)fa[i]=i,rak[i]=1;
for(int i=1;i<=m;i++)cin>>v[i].a>>v[i].b>>v[i].l;
return;
}
bool cmp(node x,node y)
{
return x.l<=y.l;
}
int main()
{
input();
sort(v+1,m+v+1,cmp);
for(int i=1;i<=m;i++)
{
if(find(v[i].a)!=find(v[i].b))
{
Union(v[i].a,v[i].b);
sum+=v[i].l;
cnt++;
}
if(cnt==n-1)break;
}
if(cnt!=n-1)
{
cout<<"orz"<<endl;
return 0;
}
cout<<sum;
return 0;
}
by mljyhp_zzx @ 2023-04-15 16:01:17
求助!!!!72分,四个RE!
by beside_the_pavilion @ 2023-04-15 16:22:40
数组开的不够大?
by Fischl322 @ 2023-05-03 22:40:47
看数据范围,数组开小了
by mljyhp_zzx @ 2023-06-03 15:18:20
谢谢