Fibonacci Tree

题目连接：

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

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 <= 105) and M(0 <= M <= 105).

　　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

Hint

题意

给你一个由白边和黑边组成的图，问你能不能找到一个生成树，使得白边的个数是Fibonacci数

题解：

考虑白边最多情况的生成树时候白边数量为Max，最少的时候为Min

那么[Min,Max]这个区间内的白边数量都可以取到

所以求出Min和Max即可

坑点：图不联通

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5+7;

struct node{

    int x,y,z;

}p[maxn];

bool cmp1(node A,node B){

    return A.z<B.z;

}

bool cmp2(node A,node B){

    return A.z>B.z;

}

int fa[maxn];

int fi(int x){

    return x==fa[x]?x:fa[x]=fi(fa[x]);

}

void uni(int x,int y){

    x=fi(x),y=fi(y);

    if(x==y)return;

    else fa[x]=fa[y];

}

void solve(int Cas){

    int n,m;

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

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

        fa[i]=i;

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

        scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);

    sort(p+1,p+1+m,cmp1);

    int x1=0,x2=0;

    int D = 0;

    for(int i=1;i<=m;i++){

        if(fi(p[i].x)!=fi(p[i].y)){

            x1+=p[i].z;

            uni(p[i].x,p[i].y);

            D = D + 1;

        }

    }

    if(D!=n-1){

        printf("Case #%d: No\n",Cas);

        return;

    }

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

        fa[i]=i;

    sort(p+1,p+1+m,cmp2);

    for(int i=1;i<=m;i++){

        if(fi(p[i].x)!=fi(p[i].y)){

            x2+=p[i].z;

            uni(p[i].x,p[i].y);

        }

    }

    long long a=1,b=1;

    int flag = 0;

    while(a<=x2||b<=x2){

        if(a>=x1&&a<=x2)

            flag=1;

        if(b>=x1&&b<=x2)

            flag=1;

        a=a+b;

        if(a>b)swap(a,b);

    }

    if(a>=x1&&a<=x2)

        flag=1;

    if(b>=x1&&b<=x2)

        flag=1;

    if(flag)printf("Case #%d: Yes\n",Cas);

    else printf("Case #%d: No\n",Cas);

}

int main(){

    int t;

    scanf("%d",&t);

    for(int cas=1;cas<=t;cas++)solve(cas);

}