Fibonacci Tree
hdu4786:http://acm.hdu.edu.cn/showproblem.php?pid=4786
题意：给你一个无向图，然后其中有的边是白色的有的边是黑色的。然后问你是否存在一棵生成树，在这课生成树上白色边的数量是一个斐波那契数。
题解：完全没有那样的思想，一道现场水题，就是不会啊，实力太弱 啊。注定打铁啊。这一题是这样的，采用极端思维：就是分别用白色和黑色优先的边去求生成树，得到一个白色数量的区间。这里需要理解的是，白色边的数目，可以在这个区间内变化。也就是构成生成树的白色边的数量在这个区间内，如果这个区间内的数没有一个是斐波那契数，那么就不可能了。同时处理出1e5以内的斐波那契数。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 const int N=2e5+10; 7 int fa[N],f[40],vis[N]; 8 int n,m,u,v,w; 9 struct Node{ 10 int u,v; 11 int w; 12 bool operator<(const Node a)const { 13 return w>a.w; 14 } 15 }edge1[N]; 16 struct Node1{ 17 int u,v; 18 int w; 19 bool operator<(const Node1 a)const { 20 return w<a.w; 21 } 22 }edge2[N]; 23 void init(){ 24 for(int i=1;i<=n;i++) 25 fa[i]=i; 26 } 27 int Find(int x){ 28 int s; 29 for(s=x;s!=fa[s];s=fa[s]); 30 while(x!=s){ 31 int temp=fa[x]; 32 fa[x]=s; 33 x=temp; 34 } 35 return s; 36 } 37 int solve1(){//黑色优先 38 int ct=0,num=0; 39 for(int i=1;i<=m;i++){ 40 int u=Find(edge1[i].u); 41 int v=Find(edge1[i].v); 42 if(u!=v){ 43 fa[u]=v; 44 if(edge1[i].w==1) 45 ct++; 46 num++; 47 } 48 if(num==n-1) 49 return ct; 50 } 51 return 0; 52 } 53 int solve2(){ 54 init(); 55 int ct=0,num=0; 56 for(int i=1;i<=m;i++){ 57 int u=Find(edge2[i].u); 58 int v=Find(edge2[i].v); 59 if(u!=v){ 60 fa[u]=v; 61 if(edge2[i].w==1) 62 ct++; 63 num++; 64 } 65 if(num==n-1) 66 return ct; 67 } 68 return 0; 69 } 70 int main(){ 71 int T,tt=1; 72 scanf("%d",&T); 73 while(T--){ 74 scanf("%d%d",&n,&m); 75 init(); 76 for(int i=1;i<=m;i++){ 77 scanf("%d %d %d",&u,&v,&w); 78 edge1[i].u=u;edge1[i].v=v;edge1[i].w=w; 79 edge2[i].u=u;edge2[i].v=v;edge2[i].w=w; 80 } 81 sort(edge1+1,edge1+m+1); 82 sort(edge2+1,edge2+m+1); 83 int ll=solve2(); 84 int rr=solve1(); 85 memset(f,0,sizeof(f)); 86 memset(vis,0,sizeof(vis)); 87 f[0]=0;f[1]=1; 88 for(int i=2;i<=21;i++){ 89 f[i]=f[i-1]+f[i-2]; 90 vis[f[i]]=1; 91 } 92 bool flag=false; 93 for(int i=ll;i<=rr;i++) 94 if(vis[i]){ 95 flag=true; 96 break; 97 } 98 if(flag)printf("Case #%d: Yes ",tt++); 99 else 100 printf("Case #%d: No ",tt++); 101 } 102 }