hdu 4786 Fibonacci Tree（最小生成树）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4786

解题思路：

题目大意：

给你一些白色跟黑色的边，问你在这幅图里面能不能找出一个生成树且里面的白边数量是Fibonacci数列的数

算法思想：

由题意，所以只要找出白边最少的生成树和白边最多的生成树的情况，然后看在这之间有没有Fibonacci数，如果有就输出yes啦，没有就输出no

因此，将白边优先和黑边优先两种顺序做两次最小生成树。

得到白边数量的区间，然后枚举斐波那契数列就可以了。

注意：如果一开始就是非连通的，直接输出NO就行了

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n,m;
struct Edge{
    int u,v,c;//1 for white and 0 for black
}edge[100005];

int fi[100];
int pa[100005];

bool cmp1(Edge a,Edge b){
    return a.c < b.c;
}

bool cmp2(Edge a,Edge b){
    return a.c > b.c;
}

void init(){
    for(int i = 0; i <= n; i++)
        pa[i] = i;
}

int findset(int x){
    if(x != pa[x])
        pa[x] = findset(pa[x]);
    return pa[x];
}

int main(){
    int tot = 2;
    fi[1] = 1;fi[2] = 2;
    while(fi[tot] <= 100000)
        fi[++tot] = fi[tot-1]+fi[tot-2];
    int T,t = 1;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i = 0; i < m; i++)
            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].c);
        init();
        sort(edge,edge+m,cmp1);
        int cnt = 0,low,high;
        int t1,t2;
        for(int i = 0; i < m; i++){
            t1 = findset(edge[i].u);
            t2 = findset(edge[i].v);
            if(t1 != t2){
                pa[t1] = t2;
                if(edge[i].c == 1)
                    cnt++;
            }
        }
        low = cnt;
        init();
        sort(edge,edge+m,cmp2);
        cnt = 0;
        for(int i = 0; i < m; i++){
            t1 = findset(edge[i].u);
            t2 = findset(edge[i].v);
            if(t1 != t2){
                pa[t1] = t2;
                if(edge[i].c == 1)
                    cnt++;
            }
        }
        high = cnt;
        int flag = 1,root = findset(1);
        for(int i = 1; i <= n; i++){
            if(findset(i) != root){
                flag = 0;
                break;
            }
        }
        if(!flag){
             printf("Case #%d: No\n",t++);
             continue;
        }
        flag = 0;
        for(int i = 1; i <= tot; i++){
            if(fi[i] >= low && fi[i] <= high){
                flag = 1;
                break;
            }
        }
        if(flag)
            printf("Case #%d: Yes\n",t++);
        else
            printf("Case #%d: No\n",t++);
    }
}