Problem Description

　　Coach Pang is interested in Fibonacci numbers while Uncle Yang wants him to do some research on Spanning Tree. So Coach Pang decides to solve the following problem:

　　Consider a bidirectional graph G with N vertices and M edges. All edges are painted into either white or black. Can we find a Spanning Tree with some positive Fibonacci number of white edges?

(Fibonacci number is defined as 1, 2, 3, 5, 8, ... )

 

Input

　　The first line of the input contains an integer T, the number of test cases.

　　For each test case, the first line contains two integers N(1 <= N <= 10⁵) and M(0 <= M <= 10⁵).

　　Then M lines follow, each contains three integers u, v (1 <= u,v <= N, u<> v) and c (0 <= c <= 1), indicating an edge between u and v with a color c (1 for white and 0 for black).

 

Output

　　For each test case, output a line “Case #x: s”. x is the case number and s is either “Yes” or “No” (without quotes) representing the answer to the problem.

 

Sample Input

2

4 4

1 2 1

2 3 1

3 4 1

1 4 0

5 6

1 2 1

1 3 1

1 4 1

1 5 1

3 5 1

4 2 1

 

Sample Output

Case #1: Yes

Case #2: No

 

Source

2013 Asia Chengdu Regional Contest

题意：问构成的生成树当中是否存在黑色边（边为1）数为斐波那契数

思路：求出生成树中最小包括的黑色边数。和最多黑色边数，假设有斐波那契数在两者之间，则能够构成。由于黑白边能够搭配使用

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n,m;

int fibo[50];

int f[100010];

struct node

{

    int u,v,c;

} s[100010];

bool cmp1(node x , node y)

{

    return x.c < y.c;

}

bool cmp2(node x, node y)

{

    return  x.c > y.c;

}

int find(int x)

{

    return x == f[x] ? x : f[x] = find(f[x]);

}

void Union(int x ,int y)

{

    int fx = find(x);

    int fy = find(y);

    if(fx != fy)

    {

        f[fx] = fy;

    }

}

int main()

{

#ifdef xxz

    freopen("in.txt","r",stdin);

#endif

    fibo[1] = 1;

    fibo[2] = 2;

    for(int i = 3; ; i++)

    {

        fibo[i] = fibo[i-1] + fibo[i-2];

        if(fibo[i] >= 100000) break;

    }

    int T,Case = 1;;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        for(int i = 1; i <= n; i++) f[i] = i;

        for(int i = 0; i < m; i++)

        {

            scanf("%d%d%d",&s[i].u,&s[i].v,&s[i].c);

            Union(s[i].u,s[i].v);

        }

        int cent = 0;

        int bl = 0, bh = 0;

        int root = 0,size = 0;

        for(int i = 1; i <= n; i++)

        {

            if(f[i] == i)

            {

                cent++;

                root = i;

            }

        }

        printf("Case #%d: ",Case++);

        if(cent >= 2) cout<<"No"<<endl;//首先要推断能否构成一个生成树。推断根节点个数是否为1即可

        else

        {

            sort(s,s+m,cmp1);

            for(int i = 1; i <= n; i++) f[i] = i;

            for(int i = 0; i < m; i++)

            {

                int fu = find(s[i].u);

                int fv = find(s[i].v);

                if(fu == fv) continue;

                bl += s[i].c;

                size++;

                Union(s[i].u,s[i].v);

                if(size == n-1) break;

            }

            size = 0;

            sort(s,s+m,cmp2);

            for(int i = 1; i <= n; i++) f[i] = i;

            for(int i = 0; i < m; i++)

            {

                int fu = find(s[i].u);

                int fv = find(s[i].v);

                if(fu == fv) continue;

                bh += s[i].c;

                size++;

                Union(s[i].u,s[i].v);

                if(size == n-1) break;

            }

            int flag = 0;

            for(int i =1; fibo[i] <= 100000 ; i++ )

            {

                if(fibo[i] >= bl && fibo[i] <= bh)

                {

                    flag = 1;

                    break;

                }

            }

            if(flag) printf("Yes\n");

            else printf("No\n");

        }

    }

}