HDU 4786 生成树 并查集+极大极小值 黑白边 确定选择白边的数量

题意：

给定一个无向图

n 个点 m条无向边

u v val

val == 1 表示边(u, v) 为白边

问能否找到n个点的生成树， 使得白边数为斐波那契数

思路：

并查集求图是否连通（ 是否存在生成树）

求出 最多白边树 的 白边数量

求出 最少白边树 的 白边数量

若[最少， 最多] 区间内存在斐波那契数 ，则满足条件

（也就是说，白边的数量是连续有解的）

//YY得证

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<string>

#include<queue>

#include<string.h>

#include<map>

#include<set>

#include<stack>

#include<vector>

#include<math.h>

#include<algorithm>

#define N 101010

#define inf 10000000

using namespace std;

inline int Min(int a,int b){return a>b?b:a;}

inline int Max(int a,int b){return a<b?b:a;}

int f[N];

int find(int x){return x==f[x]?x:(f[x] = find(f[x]));}

void Union(int u, int v){

    int fu = find(u), fv = find(v);

    if(fu>fv)

        f[fu] = fv;

    else

        f[fv] = fu;

}

set<int>fib;

int n, m;

struct node{

    int u,v,c;

}edge[N];

int edgenum;

bool cmp1(node a,node b){return a.c<b.c;}

bool cmp2(node a,node b){return a.c>b.c;}

int main(){

    int T, Cas = 1;scanf("%d",&T);

    int i, j, col;

    fib.clear();

    fib.insert(1);

    fib.insert(2);

    j=1;

    for(i=2;i<=N;){

        fib.insert(i+j);

        int lala = i;

        i = i+j;

        j = lala;

    }

    while(T--){

        scanf("%d %d", &n, &m);

        for(i=1;i<=n;i++)f[i] = i;

        edgenum = 0;

        while(m--){

            int u,v;

            scanf("%d %d %d",&u,&v,&col);

            edge[edgenum].u = u;

            edge[edgenum].v = v;

            edge[edgenum++].c = col;

            int fx = find(u), fy = find(v);

            if(fx == fy)continue;

            Union(fx,fy);

        }

        printf("Case #%d: ",Cas++);

        for(i=1;i<=n;i++)find(i);

        bool su = true;

        for(i=1;i<=n;i++)

            if(f[i]!=f[1])

            {su = false; break;}

            if(su == false)

            {printf("No\n");continue;}

            for(i=1;i<=n;i++)f[i] = i;

            sort(edge, edge+edgenum, cmp1);

            int size = 0, bl=0, bm=0;

            for(i=0;i<edgenum;i++)

            {

                int u =edge[i].u, v=edge[i].v;

                int fu = find(u), fv=find(v);

                if(fu == fv)continue;

                size++;

                bl+= edge[i].c;

                Union(fu, fv);

                if(size==n-1)break;

            }

            for(i=1;i<=n;i++)f[i] = i;

            sort(edge, edge+edgenum, cmp2);

            size = 0;

            for(i=0;i<edgenum;i++)

            {

                int u =edge[i].u, v=edge[i].v;

                int fu = find(u), fv=find(v);

                if(fu == fv)continue;

                size++;

                bm+= edge[i].c;

                Union(fu, fv);

                if(size==n-1)break;

            }

            if(fib.upper_bound(bl) == fib.end() ){printf("No\n");continue;}

            if((*fib.lower_bound(bl) )>bm){printf("No\n");continue;}

            printf("Yes\n");

    }

    return 0;

}

/*

4 2

1 2 1

3 4 1

*/