首页 > 代码库 > Hdu4786
Hdu4786
Fibonacci Tree
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2340 Accepted Submission(s): 748
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
Source
2013 Asia Chengdu Regional Contest
题意:问构成的生成树其中是否存在黑色边(边为1)数为斐波那契数
思路:求出生成树中最小包含的黑色边数,和最多黑色边数,如果有斐波那契数在两者之间,则可以构成,因为黑白边可以搭配使用
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> using namespace std; int n,m; int fibo[50]; int f[100010]; struct node { int u,v,c; } s[100010]; bool cmp1(node x , node y) { return x.c < y.c; } bool cmp2(node x, node y) { return x.c > y.c; } int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); } void Union(int x ,int y) { int fx = find(x); int fy = find(y); if(fx != fy) { f[fx] = fy; } } int main() { #ifdef xxz freopen("in.txt","r",stdin); #endif fibo[1] = 1; fibo[2] = 2; for(int i = 3; ; i++) { fibo[i] = fibo[i-1] + fibo[i-2]; if(fibo[i] >= 100000) break; } int T,Case = 1;; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) f[i] = i; for(int i = 0; i < m; i++) { scanf("%d%d%d",&s[i].u,&s[i].v,&s[i].c); Union(s[i].u,s[i].v); } int cent = 0; int bl = 0, bh = 0; int root = 0,size = 0; for(int i = 1; i <= n; i++) { if(f[i] == i) { cent++; root = i; } } printf("Case #%d: ",Case++); if(cent >= 2) cout<<"No"<<endl;//首先要判断是否能构成一个生成树,判断根节点个数是否为1就行 else { sort(s,s+m,cmp1); for(int i = 1; i <= n; i++) f[i] = i; for(int i = 0; i < m; i++) { int fu = find(s[i].u); int fv = find(s[i].v); if(fu == fv) continue; bl += s[i].c; size++; Union(s[i].u,s[i].v); if(size == n-1) break; } size = 0; sort(s,s+m,cmp2); for(int i = 1; i <= n; i++) f[i] = i; for(int i = 0; i < m; i++) { int fu = find(s[i].u); int fv = find(s[i].v); if(fu == fv) continue; bh += s[i].c; size++; Union(s[i].u,s[i].v); if(size == n-1) break; } int flag = 0; for(int i =1; fibo[i] <= 100000 ; i++ ) { if(fibo[i] >= bl && fibo[i] <= bh) { flag = 1; break; } } if(flag) printf("Yes\n"); else printf("No\n"); } } }
Hdu4786
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。