求助!!!!72分,四个RE!
查看原帖
求助!!!!72分,四个RE!
371925
Cosmos_zzx楼主2023/4/15 15:57
#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;
}
2023/4/15 15:57
加载中...