HDU 4786 Fibonacci Tree

Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

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

Sample Output

Case #1: Yes
Case #2: No

/*
题意：
给你一个图，每条边有两种颜色黑色或者白色，让你判断存不存在一棵生成树，使得白边的数量为斐波那契数。
分别求出白边在生成树中的最大值和最小值，用生成树思想来做。
当然如果图不是连通图的话，则肯定输出No。然后判断在这个最大最小之间存不存斐波那契数，如果存在则Yes，否则No。因为在这个区间内总能找到一条白边可以用黑边来代替。


这题我刚开始用的是Prim算法，但是这题边数有100000条，就TLE了，难过。。
后来改用kruskal，马上就过了。。诶
*/
#include <iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int team[100005],a[30];
struct node
{
    int x,y,z;
}edge[100005];
int n,m,summax,summin,t,len;

bool cmp1(node a,node b) //从小到大排列
{
    return a.z<b.z;
}
bool cmp2(node a,node b)//从大到小排列
{
    return a.z>b.z;
}
int findteam(int k)//并查集
{
    if (team[k]==k) return k;
     else
     {
         team[k]=findteam(team[k]);
         return team[k];
     }
}

void primmin()//求最小生成树，求summin
{
    sort(edge+1,edge+m+1,cmp1);
    for(int i=1;i<=m;i++)
    {
        int teamx=findteam(edge[i].x);
        int teamy=findteam(edge[i].y);
        if (teamx==teamy) continue;
        summin+=edge[i].z;
        team[teamx]=teamy;
    }
}
void primmax()//求最大生成树，求summax
{
    sort(edge+1,edge+m+1,cmp2);
    for(int i=1;i<=m;i++)
    {
        int teamx=findteam(edge[i].x);
        int teamy=findteam(edge[i].y);
        if (teamx==teamy) continue;
        summax+=edge[i].z;
        team[teamx]=teamy;
    }
}
void prework()//把小于10^5次的菲波那切数列求出来
{
    len=2;
    a[1]=a[2]=1;
    for(len=3;a[len-1]<100000;len++) a[len]=a[len-1]+a[len-2];
    len--;
}
bool ok()//判断能不能连通
{
    int x=findteam(team[1]);
    for(int i=2;i<=n;i++)
    {
        int y=findteam(team[i]);
        if (x!=y) {printf("No
"); return 0;}
    }
    return 1;
}

int main()
{
    prework();
    scanf("%d",&t);
    for(int ii=1;ii<=t;ii++)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
            scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);

        printf("Case #%d: ",ii);
        summin=summax=0;
        for(int i=1;i<=n;i++) team[i]=i;
        primmin();
        if (!ok()) continue;
        for(int i=1;i<=n;i++) team[i]=i;
        primmax();
        if (!ok()) continue;

        for(int i=1;i<=len;i++)
        {
            if (a[i]>=summin && a[i]<=summax)  {printf("Yes
");break;}
            if (a[i]>summax) {printf("No
");break;}
        }
    }
    return 0;
}