﻿HDU 4786 Fibonacci Tree(Kruskal)-Ocrosoft

# Fibonacci Tree

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4187    Accepted Submission(s): 1304

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 <= 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
```

Solution

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 100000+10
using namespace std;
int n,m;
int pre[MAXN];
struct Edge
{
int u,v,s;
} edge[MAXN];
int find(int x)
{
if(pre[x]!=x)pre[x]=find(pre[x]);
return pre[x];
}
int Kruskal(int s)
{
int sum=0;
for(int i=0; i<=n; i++)pre[i]=i;
for(int i=1; i<=m; i++)
{
if(edge[i].s!=s)
{
int x=find(edge[i].u);
int y=find(edge[i].v);
if(x!=y)
{
pre[x]=y;
sum++;
}
}
}
return sum;
}
int Fiboacii[MAXN]= {1,2};
int main()
{
for(int i=2;; i++)
{
Fiboacii[i]=Fiboacii[i-1]+Fiboacii[i-2];
if(Fiboacii[i]>MAXN)break;
}
int T,kase=0;
cin>>T;
while(T--)
{
printf("Case #%d: ",++kase);
cin>>n>>m;
for(int i=1; i<=m; i++)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].s);
if(Kruskal(2)!=n-1)printf("No\n");
else
{
int maxn=Kruskal(0);
int minn=n-Kruskal(1)-1;
bool flag=0;
for(int i=0; Fiboacii[i]<=maxn&&!flag; i++)
if(Fiboacii[i]>=minn&&Fiboacii[i]<=maxn)flag=1;
if(flag)printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
```