题目： http://acm.hdu.edu.cn/showproblem.php?pid=4786
题意: 存不存在所含白边数为菲波那契数的生成树（包含图中所有节点）。
找出生成树中所含白边最多和最少的生成树中所含白边数， 就是按照边的黑白排一下序， 组成一个区间[a, b]； 然后在区间[a, b]中枚举菲波那契数。 参考bin神代码。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> 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 "); 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 "); else printf("No "); } return 0; }