求调,生成树模板
  • 板块灌水区
  • 楼主MWL_wma
  • 当前回复3
  • 已保存回复6
  • 发布时间2023/11/24 20:02
  • 上次更新2023/11/24 21:50:38
查看原帖
求调,生成树模板
1023017
MWL_wma楼主2023/11/24 20:02
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[5002],z,n1;
struct UIiyTYYTTYytyiyTYIGFB{
	int v;
	int x,y;
}l[200002];
bool px(UIiyTYYTTYytyiyTYIGFB a,UIiyTYYTTYytyiyTYIGFB b){return a.v<b.v;}
int find(int x){
	if(x==fa[x]){
		return x;
	}
	return fa[x]=find(fa[x]);
}
int main(){
	scanf("%d%d",&n,&m);
	n1=n;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&l[i].x,&l[i].y,& l[i].v);
	}
	sort(l+1,l+1+m,px);
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x1=find(l[i].x),y1=find(l[i].y);
		if(x1-y1){
			fa[l[i].x]=l[i].y;
			z+=l[i].v;
			--n1;
		}
	}
	if(n1==1){
		printf("%d",z);
	}else{
		puts("orz");
	}
	return 0;
}

https://www.luogu.com.cn/problem/P3366

玄关,谢谢

2023/11/24 20:02
加载中...