[kruskal]hdoj 4786

大致题意：

       一个无向图中，每条边都是白边或者是黑边中的一种，问是否存在这个图的一颗生成树使得生成树中白边的个数为一个斐波那契数。

 

大致思路：

      求出生成树中白边可能的最大值和最小值，如果某个斐波那契数包含在最大值和最小值之间，则可判定存在这样的生成树。

       要注意判定这个图是否联通

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int nMax = 100020;

struct data{     // 每条边的数据结构。
    int u, v, w;
}edge[nMax];
int n, m, pa[nMax];

bool cmp(data a, data b){
    if(a.w < b.w) return true;
    return false;
}
bool cmp1(data a, data b){
    if(a.w > b.w) return true;
    return false;
}

void make_set(){       // 并查集：建立。
    for(int x = 1; x <= n; x ++)
        pa[x] = x;
}

int find_set(int x){   // 并查集：查找。
    if(x != pa[x])
        pa[x] = find_set(pa[x]);
    return pa[x];
}

int kruskal(int f){
    int i, ans = 0;
    make_set();
    if(f)sort(edge, edge + m, cmp);  //  对所有边按照权值从小到大排序。
    else sort(edge, edge + m, cmp1);
    for(i = 0; i < m; i ++){
        int x = find_set(edge[i].v);
        int y = find_set(edge[i].u);
        if(x != y){            
            pa[y] = x;
            ans += edge[i].w;
        }
    }
    return ans;
}

int fib[25]={1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,28657,46368,75025,121393};
int main(){
    int i,k,t,ttt;
    scanf("%d",&ttt);
    for(t=1;t<=ttt;t++){
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++){
            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
        }
        int a=kruskal(1);
        int b=kruskal(0);

        if(a>=b){
            k=a,a=b,b=k;
        }

        bool flag=1;

        for(i=2;i<=n;i++){
            if(find_set(i)!=find_set(1)){
                flag=0;
                break;
            }
        }
        if(!flag){
            printf("Case #%d: No\n",t);
            continue;
        }
        flag=0;
        for(i=0;i<24;i++){
            if(a<=fib[i]&&b>=fib[i]){
                flag=1;
                break;
            }
        }
        if(flag)printf("Case #%d: Yes\n",t);
        else printf("Case #%d: No\n",t);
    }
}