P3366为什么3个点re
查看原帖
P3366为什么3个点re
311478
__gcd__楼主2021/9/11 22:38
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
	int a,b,c;
}s[11000];
int f[11000];
int cmp(node n1,node n2){
	if(n1.c<n2.c)
	  return 1;
	return 0;
}
int find(int x){
	if(f[x]!=x)
	  return f[x]=find(f[x]);
	else
	  return x;
}
int main(){
	int n,m,x,y,ans=0,t=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	  f[i]=i;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);
	sort(s+1,s+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int fx=find(s[i].a),fy=find(s[i].b);
		if(fx!=fy){
			ans+=s[i].c;
			f[fx]=fy;
			t++;
			if(t==n-1)
			{
				cout<<ans;
				return 0;
			}
		}
	}
	cout<<"orz";
}
2021/9/11 22:38
加载中...