HDU - 4786 - Fibonacci Tree

左手的ㄟ右手 2022-06-10 00:52 93阅读 0赞

--------------------

题目连接：[http://acm.hdu.edu.cn/showproblem.php?pid=4786][http_acm.hdu.edu.cn_showproblem.php_pid_4786]

## 题目描述 ##

### 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, … )

一个图，N个顶点，M条边，每条边或为白色或为黑色。  
问你能否用两色边构造出一颗生成树，使树中白色边的数量为一个Fibonacci数。  
( Fibonacci数定义为 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).  
第一行输入一个整数T，表示样例个数。

每个样例第一行包括两个整数 N(1 <= N <= 10^5) and M(0 <= M <= 10^5) ，分别表示点和边的数量。  
接下来 M 行，每行包括三个整数 u, v (1 <= u,v <= N, u<> v)和 c (0 <= c <= 1)，表示u和v之间有一条颜色为c的边（1表示白色，0表示黑色）。

### 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.

对于每个样例，输出一行“Case \#x: s”。x表示第几个样例， s表示答案（“Yes” 或 “No”）。

### 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

## 解题思路 ##

先说一下题意，连接所有的点，最后生成 生成树 ，连接的时候用的边不是白的就是黑的（人为规定），问用的白边的条数是否是一个Fibonacci数  
第一点，没说是最小生成树  
第二点，存在就输出yes  
明白了这个点，那么我们把最小生成树用的白边和最大生成树的白边，都算出来，如果这里面有Fibonacci数的话，那么就yes，所以后面控制黑白的数字还是有用的，到时候直接加上就ok

## AC代码 ##

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #define maxn 100010
    using namespace std;
    
    int n, m;
    int pre[maxn];
    int use[40];
    
    struct node {
        int a, b, c;
        bool operator < (const node& rhs) const {  
            return c < rhs.c;  
        } 
    }cnt[maxn];
    
    int find(int x) {
        return pre[x] == x ? x : pre[x] =  find(pre[x]);
    }
    
    bool kruskal() {
        int num = 1, ans1 = 0, ans2 = 0;
        for(int i = 1; i <= n; i++) pre[i] = i;
        sort(cnt, cnt+m);
        for(int i = 0; i < m; i++) {
            int x = find(cnt[i].a);
            int y = find(cnt[i].b);
            if(x != y) {
                pre[y] = x;
                num++;
                ans1 += cnt[i].c;
            }
        }
        if(num != n) return false;
        for(int i = 1; i <= n; i++) pre[i] = i;
        for(int i = m-1; i >= 0; i--) {
            int x = find(cnt[i].a);
            int y = find(cnt[i].b);
            if(x != y) {
                pre[y] = x;
                ans2 += cnt[i].c;
            }
        }
        for(int i = 1; i <= 26; i++) 
            if(ans1 <= use[i] && use[i] <= ans2) return true;
        return false;
    }
    
    void init() {
        use[1] = 1, use[2] = 2;
        for(int i = 3; i <= 26; i++) use[i] = use[i-1] + use[i-2];
    }
    
    int main() {
        init();
        int t, kase = 1;
        scanf("%d", &t);
        while(t--) {
            scanf("%d %d" , &n, &m);
            for(int i = 0; i < m; i++) scanf("%d %d %d", &cnt[i].a, &cnt[i].b, &cnt[i].c);
            if(kruskal()) printf("Case #%d: Yes\n", kase++);
            else printf("Case #%d: No\n", kase++);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_4786]: http://acm.hdu.edu.cn/showproblem.php?pid=4786