题目： http://acm.hdu.edu.cn/showproblem.php?pid=4786
题意: 存不存在所含白边数为菲波那契数的生成树（包含图中所有节点）。
找出生成树中所含白边最多和最少的生成树中所含白边数， 就是按照边的黑白排一下序， 组成一个区间[a, b]； 然后在区间[a, b]中枚举菲波那契数。 参考bin神代码。
#include#include #include #include using namespace std; bool flag1, flag2; int sum, Y;struct Sorrow{ int a, b, c;} edge[100001];bool cmp1(Sorrow a, Sorrow b){ return a.c < b.c;}bool cmp2(Sorrow a, Sorrow b){ return a.c > b.c;}int father[100001], n;void init(){ //memset(father, -1, sizeof(father)); for(int i = 1; i <= n; i++) father[i] = i; }int Find(int a){ if(father[a] == a) return a; else return father[a] = Find(father[a]);} int mercy(int a, int b, int c){// int Y = 0; int Q = Find(a); int P = Find(b); if(Q != P) { father[Q] = P; if(c) Y++; } return Y;}bool Judge(){ int cnt = 0; for(int i = 1; i <= n; i++) if(father[i] == i) { cnt++; if(cnt > 1) return false; } return true;}int b[100001]; int Bitch(){ sum = 1; b[0] = 1; b[1] = 2; while(b[sum] < 100001) { b[sum+1] = b[sum] + b[sum-1]; sum++; }}int main(){ int T, Q = 1; scanf("%d", &T); while(T--) { int m, L, R; scanf("%d %d", &n, &m); init(); for(int i = 0; i < m; i++) scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].c); sort(edge, edge+m, cmp1); Y = 0; for(int i = 0; i < m; i++) L = mercy(edge[i].a, edge[i].b, edge[i].c); // flag1 = Judge(); init(); sort(edge, edge+m, cmp2); Y = 0; for(int i = 0; i < m; i++) R = mercy(edge[i].a, edge[i].b, edge[i].c); flag2 = Judge(); printf("Case #%d: ", Q++); if(flag2 == false) { printf("No\n"); continue; } Bitch(); bool flag = false; for(int i = 0; i < sum; i++) { if(b[i] >= L && b[i] <= R) flag = true; } if(flag) printf("Yes\n"); else printf("No\n"); } return 0; }