2023年多校联训NOIP层测试2

GOD-HJ / 2023-08-06 / 原文

T1 斐波那契树

题目

思路

题解做法：

可以先把白色边权看成1，黑色边权看成0，求最小生成树和最大生成树，判断这两个值之间是否存在一
个斐波那契数。可以证明这中间的值都是可以出现的（参考求恰好k条白边的思路，BZOJ2654）。

我的做法：
找到最小生成树和最大生成树的值。

看它们是否在

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int T,n,m,fa[N],f[30];
struct node{int from,to,w;}e[N];
inline bool cmp1(node x,node y){
	return x.w<y.w;
} 
inline bool cmp2(node x,node y){
	return x.w>y.w;
}
inline int ff(int x){
	if(x!=fa[x])
		fa[x]=ff(fa[x]);
	return fa[x];
}
inline bool kru(int &ans){
	int cnt=0;
	for(int i=1;i<=n;++i) fa[i]=i;
	for(int i=1;i<=m;++i){
		if(cnt==n-1) break;
		int x=ff(e[i].from),y=ff(e[i].to);
		if(x!=y){
			fa[x]=y;
			ans+=e[i].w;
			++cnt; 
		}
	}
	return cnt==n-1;
}
signed main(void){
	scanf("%lld",&T);
	f[1]=f[2]=1;
	for(int i=3;i<=30;++i) f[i]=f[i-1]+f[i-2]; 
	while(T--){
		int minn=0,maxx=0;
		memset(e,0,sizeof e);
		scanf("%lld%lld",&n,&m);
		for(int x,y,z,i=1;i<=m;++i){
			scanf("%lld%lld%lld",&e[i].from,&e[i].to,&e[i].w);
		}
		sort(e+1,e+m+1,cmp1);
		if(!kru(minn)){
			printf("NO\n");
			continue;
		}
		sort(e+1,e+m+1,cmp2);
		if(!kru(maxx)){
			printf("NO\n");
			continue; 
		}
		for(int i=1;;++i){
			if(f[i]>=minn&&f[i]<=maxx){
				printf("YES\n");
				break;
			}
			else if(f[i]>maxx){
				printf("NO\n");
				break;
			}
		}
	}
	return 0;
}