hdu4786:http://acm.hdu.edu.cn/showproblem.php?pid=4786
题意：给你一个无向图，然后其中有的边是白色的有的边是黑色的。然后问你是否存在一棵生成树，在这课生成树上白色边的数量是一个斐波那契数。
题解：完全没有那样的思想，一道现场水题，就是不会啊，实力太弱 啊。注定打铁啊。这一题是这样的，采用极端思维：就是分别用白色和黑色优先的边去求生成树，得到一个白色数量的区间。这里需要理解的是，白色边的数目，可以在这个区间内变化。也就是构成生成树的白色边的数量在这个区间内，如果这个区间内的数没有一个是斐波那契数，那么就不可能了。同时处理出1e5以内的斐波那契数。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=2e5+;
int fa[N],f[],vis[N];
int n,m,u,v,w;
struct Node{
int u,v;
int w;
bool operator<(const Node a)const {
return w>a.w;
}
}edge1[N];
struct Node1{
int u,v;
int w;
bool operator<(const Node1 a)const {
return w<a.w;
}
}edge2[N];
void init(){
for(int i=;i<=n;i++)
fa[i]=i;
}
int Find(int x){
int s;
for(s=x;s!=fa[s];s=fa[s]);
while(x!=s){
int temp=fa[x];
fa[x]=s;
x=temp;
}
return s;
}
int solve1(){//黑色优先
int ct=,num=;
for(int i=;i<=m;i++){
int u=Find(edge1[i].u);
int v=Find(edge1[i].v);
if(u!=v){
fa[u]=v;
if(edge1[i].w==)
ct++;
num++;
}
if(num==n-)
return ct;
}
return ;
}
int solve2(){
init();
int ct=,num=;
for(int i=;i<=m;i++){
int u=Find(edge2[i].u);
int v=Find(edge2[i].v);
if(u!=v){
fa[u]=v;
if(edge2[i].w==)
ct++;
num++;
}
if(num==n-)
return ct;
}
return ;
}
int main(){
int T,tt=;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
init();
for(int i=;i<=m;i++){
scanf("%d %d %d",&u,&v,&w);
edge1[i].u=u;edge1[i].v=v;edge1[i].w=w;
edge2[i].u=u;edge2[i].v=v;edge2[i].w=w;
}
sort(edge1+,edge1+m+);
sort(edge2+,edge2+m+);
int ll=solve2();
int rr=solve1();
memset(f,,sizeof(f));
memset(vis,,sizeof(vis));
f[]=;f[]=;
for(int i=;i<=;i++){
f[i]=f[i-]+f[i-];
vis[f[i]]=;
}
bool flag=false;
for(int i=ll;i<=rr;i++)
if(vis[i]){
flag=true;
break;
}
if(flag)printf("Case #%d: Yes\n",tt++);
else
printf("Case #%d: No\n",tt++);
}
}