首页 > 代码库 > POJ 4786 Fibonacci Tree

POJ 4786 Fibonacci Tree

2024-07-24 01:11:02   219人阅读

Fibonacci Tree

Time Limit: 2000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 4786
64-bit integer IO format: %I64d      Java class name: Main
 
　　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

24 41 2 12 3 13 4 11 4 05 61 2 11 3 11 4 11 5 13 5 14 2 1

Sample Output

Case #1: YesCase #2: No

Source

2013 Asia Chengdu Regional Contest
 
解题：最小生成树Kruskal思想。
 
 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 100010;18 struct arc {19     int u,v,c;20 };21 int uf[maxn],n,m,cnt;22 int fib[50] = {1,2};23 arc e[maxn];24 void init() {25     for(int i = 2; i < 30; i++)26         fib[i] = fib[i-1] + fib[i-2];27 }28 bool cmp1(const arc &x,const arc &y) {29     return x.c < y.c;30 }31 bool cmp2(const arc &x,const arc &y) {32     return x.c > y.c;33 }34 int Find(int x) {35     if(x == uf[x]) return uf[x];36     return uf[x] = Find(uf[x]);37 }38 int kruskal(bool flag) {39     for(int i = 0; i <= n; i++) uf[i] = i;40     int k = cnt = 0;41     if(flag) sort(e,e+m,cmp1);42     else sort(e,e+m,cmp2);43     for(int i = 0; i < m; i++) {44         int tx = Find(e[i].u);45         int ty = Find(e[i].v);46         if(tx != ty) {47             uf[tx] = ty;48             if(e[i].c) k++;49             cnt++;50         }51     }52     return k;53 }54 int main() {55     int t,x,y,cs = 1;56     init();57     scanf("%d",&t);58     while(t--) {59         scanf("%d %d",&n,&m);60         for(int i = 0; i < m; i++)61             scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].c);62         x = kruskal(true);63         if(cnt < n-1) {64             printf("Case #%d: No\n",cs++);65             continue;66         }67         y = kruskal(false);68         int *tmp = lower_bound(fib,fib+30,x);69         if(*tmp >= x && *tmp <= y) 70             printf("Case #%d: Yes\n",cs++);71         else printf("Case #%d: No\n",cs++);;72     }73     return 0;74 }
View Code

 

POJ 4786 Fibonacci Tree


联系
我们