72分,恳请各位大佬帮助
查看原帖
72分,恳请各位大佬帮助
467683
return_CE楼主2021/8/4 19:43
include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct bian
{
	int begine;
	int to;
	long long pre;
}line[200003];
int m,n,q=1,k=0;
int fat[5003];
long long tot=0;
int father(int x)
{
	if(fat[x]!=x) fat[x]=father(fat[x]);
	return fat[x];	
}
void unionn(int x,int y)
{
	int fa=father(x);
	int fb=father(y);
	if(fa!=fb) fat[fa]=fb;
}
long long cmp(bian a,bian b)
{
	if(a.pre<=b.pre) return 1;
	else return 0;
}
int change(int x,int y);
int main()
{
	int log=0;
	freopen("in.txt","r",stdin);
	freopen("o.txt","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++) scanf("%d%d%lld",&line[i].begine,&line[i].to,&line[i].pre);
	sort(line+1,line+m+1,cmp);
	for(int i=1;i<=n;i++) fat[i]=i;
		for(int i=1;i<=m;i++){
		if(father(line[i].begine)!=father(line[i].to)){
			unionn(line[i].begine,line[i].to);
			tot+=line[i].pre;
			k++;
		}
		if(k==n) break;
	}
	if(k<n) cout<<"orz";
		else cout<<tot;
	return 0;
}
2021/8/4 19:43
加载中...