HDU - 4786 Fibonacci Tree（最小生成树 + 最大生成树）

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

Sample Output

Case #1: Yes
Case #2: No

题意：给定一棵树，边的颜色为白色或黑色，问是否有白边数为斐波那契数的生成树。

思路：把白边排在前面，求最小生成树可以得到白边最多的情况，把黑边排在前面，再求最小生成树可以得到白边最少的情况。判断两个数中间有没有斐波那契数。

0表示黑白，1表示白边，把白边排在前面相当于求最大生成树，把黑边排在前面相当于求最小生成树。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;

int father[N];
bool vis[N];
int n, m, tot, maxx, minn;

struct node {
    int u,v,w;
}edge[N];

bool cmp1(node a, node b) { ///白边在前
    return a.w > b.w;
}

bool cmp2(node a, node b) { ///黑边在前
    return a.w < b.w;
}

void init() {
    memset(vis, 0, sizeof(vis));
    ll a = 1, b = 1;
    vis[1] = 1;
    while(b < N) {
        ll tmp = a + b;
        a = b;
        b = tmp;
        vis[b] = 1;
    }
}

int Find(int x) {
    if(x == father[x])
        return x;
    return father[x] = Find(father[x]);
}

void Union(int x,int y) {
    int tmpx=Find(x);
    int tmpy=Find(y);
    if(tmpx!=tmpy)
    {
        father[tmpx]=tmpy;
    }
}

int kruskal() {
    for(int i = 1; i <= n; i++)
        father[i] = i;
    node now;
    int ans = 0;
    for(int i = 1; i <= m; ++i) {
        now = edge[i];
        if(Find(now.u) != Find(now.v)) {
            Union(now.u, now.v);
            ans += now.w;
        }
    }
    return ans;
}

int main()
{
    init();
    int t, u, v, k, kcase = 0;
    scanf("%d", &t);
    while(t--) {
        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);
        }

        sort(edge + 1, edge + m + 1, cmp1);
        maxx = kruskal();
        int cnt = 0;
        for(int i = 1; i <= n; ++i) {
            if(father[i] == i) {
                cnt++;
                if(cnt > 1) break;
            }
        }
        if(cnt > 1) {
            printf("Case #%d: No\n", ++kcase);
            continue;
        }

        sort(edge + 1, edge + m + 1, cmp2);
        minn = kruskal();
        cnt = 0;
        for(int i = 1; i <= n; ++i) {
            if(father[i] == i) {
                cnt++;
                if(cnt > 1) break;
            }
        }
        if(cnt > 1) {
            printf("Case #%d: No\n", ++kcase);
            continue;
        }
//        cout<<minn<<' '<<maxx<<'\n';
        bool flag = 0;
        for(int i = minn; i <= maxx; ++i) {
            if(vis[i]) {
                flag = 1;
                break;
            }
        }
        if(flag) printf("Case #%d: Yes\n", ++kcase);
        else printf("Case #%d: No\n", ++kcase);
    }
    return 0;
}