Fibonacci Tree
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
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).
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
生成树的深入理解，也就是说：
（1）白边的最小条数（L）与最大条数（R）是一个定值 ；
（2）黑边可以由白边替换。
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int Max_N = ;
struct Edge{
int u ;
int v ;
int w ;
} ;
Edge edge[Max_N] ;
int N , M; bool cmp1(Edge A ,Edge B){
return A.w < B.w ;
} bool cmp2(Edge A ,Edge B){
return A.w > B.w ;
} int father[Max_N] ; int find_father(int x){
if(x == father[x])
return x ;
else
return father[x] = find_father(father[x]) ;
} int gao(){
int sum = ,brige = ;
for(int i = ; i <= N ; i++)
father[i] = i ;
for(int i = ; i <= M ; i++){
int f_u = find_father(edge[i].u) ;
int f_v = find_father(edge[i].v) ;
if(f_u != f_v){
brige ++ ;
sum += edge[i].w ;
father[f_u] = f_v ;
}
if(brige == N-)
break ;
}
return brige == N- ? sum : - ;
} int fibo[] ; void init_fibo(){
fibo[] = ;
fibo[] = ;
for(int i = ; i <= ; i++)
fibo[i] = fibo[i-] + fibo[i-] ;
} int judge(){
int L , R ;
sort(edge+ ,edge++M, cmp1) ;
L = gao() ;
sort(edge+ ,edge++M ,cmp2) ;
R = gao() ;
if(L == -)
return ;
for(int i = ;i < ;i++){
if(L <= fibo[i] && fibo[i] <= R)
return ;
}
return ;
} int main(){
init_fibo() ;
int T ;
scanf("%d",&T) ;
for(int cas = ;cas <= T; cas++){
scanf("%d%d",&N,&M) ;
for(int i = ;i <= M ;i++)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w) ;
printf("Case #%d: %s\n",cas,judge()? "Yes" : "No") ;
}
return ;
}