题目链接：

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

题意：

N个顶点,M条边。每条边或为白色或为黑色（ 1 or 0 ）。

问有没实用是斐波那契数的数目的白色边构成一棵生成树。

PS:

事实上说是并查集更靠谱一点的酱紫！

首先推断整个图是否是连通的，若不连通则直接输出No。

接下来首先仅讨论白边。不要黑边，看最多能增加多少条白边。使得不存在环。

这样我们得到了能增加白边的最大值max。（就是全部生成树里白边数量的最大值）。

接下来同理仅讨论黑边，这样我们能够得到可增加白边的最小值min。（也能够觉得是全部生成树中白边的最小值）。

然后我们仅仅要推断这两个值之间是否存在斐波那契数即可了。

代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn = 100017;struct node{    int u, v;    int c;} a[maxn];int f[maxn], Fib[maxn];int n, m;int findd(int x){    return x==f[x] ? x : f[x]=findd(f[x]);}int kruskal(int sign){    int k = 0;    //sort(a,a+m,cmp);    for(int i = 0; i <= n; i++)    {        f[i] = i;    }    for(int i = 1; i <= m; i++)    {        if(a[i].c != sign)        {            int f1 = findd(a[i].u);            int f2 = findd(a[i].v);            if(f1 != f2)            {                f[f1] = f2;                k++;            }        }    }    return k;}void init(){    Fib[0] = 1, Fib[1] = 2;    for(int i = 2; ; i++)    {        Fib[i] = Fib[i-1]+Fib[i-2];        if(Fib[i] > maxn)            break;    }}int main(){    int t;    int cas = 0;    init();    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&n,&m);        for(int i = 1; i <= m; i++)        {            scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].c);        }        int ans = kruskal(2);        if(ans != n-1)//不能形成树        {            printf("Case #%d: No\n",++cas);            continue;        }        int maxx = kruskal(0);        int minn = n-1-kruskal(1);        int flag = 0;        for(int i = 0; ; i++)        {            if(Fib[i] >=minn && Fib[i]<=maxx)            {                flag = 1;                break;            }            if(Fib[i] > maxx)            {                break;            }        }        if(flag)        {            printf("Case #%d: Yes\n",++cas);        }        else        {            printf("Case #%d: No\n",++cas);        }    }    return 0;}