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, ... )
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 = 100008 ; 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 = 0 ,brige = 0 ; for(int i = 1 ; i <= N ; i++) father[i] = i ; for(int i = 1 ; 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-1) break ; } return brige == N-1 ? sum : -1 ; } int fibo[31] ; void init_fibo(){ fibo[1] = 1 ; fibo[2] = 2 ; for(int i =3 ; i <= 30 ; i++) fibo[i] = fibo[i-1] + fibo[i-2] ; } int judge(){ int L , R ; sort(edge+1 ,edge+1+M, cmp1) ; L = gao() ; sort(edge+1 ,edge+1+M ,cmp2) ; R = gao() ; if(L == -1) return 0 ; for(int i =1 ;i < 30 ;i++){ if(L <= fibo[i] && fibo[i] <= R) return 1 ; } return 0 ; } int main(){ init_fibo() ; int T ; scanf("%d",&T) ; for(int cas =1 ;cas <= T; cas++){ scanf("%d%d",&N,&M) ; for(int i = 1 ;i <= M ;i++) scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w) ; printf("Case #%d: %s ",cas,judge()? "Yes" : "No") ; } return 0; }