21pts求助
查看原帖
21pts求助
1135072
uwutongshu楼主2025/2/6 20:56
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int Set[5010],r[5010];
struct pi{
	int x1,y1,z;
}h[200010];
bool cmp(pi a,pi b){
	return a.z<b.z;
}
int find(int x)
{
	int r=x;
	while(Set[r]!=r) r=Set[r];
	return r;
}
void bin(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(r[fx]>r[fy]) Set[fy]=fx;
	else
	{
		Set[fx]=fy;
		if(r[fx]==r[fy]) r[fy]++;
	} 
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n,m;
	int ans=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++) Set[i]=i,r[i]=1;
	for(int i=1;i<=m;i++)
	cin>>h[i].x1>>h[i].y1>>h[i].z;
	sort(h+1,h+1+m,cmp);
	int l=1;
	for(int i=1;i<=n;i++)
	{
		if(find(h[i].x1)==find(h[i].y1)) continue;
		ans+=h[i].z; 
		bin(h[i].x1,h[i].y1);
		l++;
		if(l==n) break;
	}
	for(int i=2;i<=n;i++)
	{
		if(find(h[i].x1)!=find(h[i].y1))
		{
			cout<<"orz";
			return 0;
		}
	}
	cout<<ans;
	return 0;
}
2025/2/6 20:56
加载中...