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;
}