hdoj 4786 Fibonacci Tree 【生成树+想法】

柔情只为你懂 2022-08-13 09:59 13阅读 0赞

题目：[hdoj 4786 Fibonacci Tree][]

题意：给出 n 个点 m 条边的图，边只有两种颜色，白色和黑色，让你判断能不能让一个生成树中白边的个数为斐波那契数。

分析：这是个想法题目，前提是知道生成树的定义：生成树必须是所有点都在树中

那么既然要是斐波那契数，我只要把白色边的最大个数和最小个数求出来，如果这个范围内有斐波那契数的话，那么就满足条件。

当然这样求的前提条件是期间的所有的生成树都是满足条件的。即都是满足能够生成树的。

ok，AC代码：

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<queue>
    #include<stack>
    #define MAXN 100005
    using namespace std;
    struct node
    {
        int x,y,val;
    } a[MAXN];
    int fb[MAXN];
    int father[MAXN];
    void isit()
    {
        memset(fb,0,sizeof(fb));
        int a = 1,b = 1;
        fb[1] = 1;
        for(int c = a+b;c<=MAXN; c=b+a)
        {
            fb[c] = 1;
            a = b;
            b = c;
        }
    }
    bool cmp(node a,node b)
    {
        return a.val<b.val;
    }
    int Find(int u)
    {
          if (father[u]==u) return u;
          return father[u]=Find(father[u]);
    }
    int Yougth(int n,int m,int x)
    {
        for(int i=1;i<=n;i++)
            father[i] = i;
        int ans = 0;
        int start = m-1;
        if(x==1)
            start = 0;
        for(int i=start;i>=0 && i<m ;i+=x)
        {
            int s = Find(a[i].x) ,t = Find(a[i].y);
            //printf("%d %d %d %d\n",father[a[i].x],father[a[i].y],a[i].x,t);
            if(s == t)
                continue;
            father[s]=t;
            ans+=a[i].val;
        }
        int tmp = Find(1);
        for(int i=2;i<=n;i++)
            if(Find(i)!=tmp)
                return 10;
        return ans;
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int T;
        isit();
        scanf("%d",&T);
        for(int cas=1;cas<=T;cas++)
        {
            int n,m;
            scanf("%d%d",&n,&m);
            for(int i=0;i<m;i++)
                scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].val);
            sort(a,a+m,cmp);
            int r = Yougth(n,m,-1),l = Yougth(n,m,1);
            //printf("%d %d\n",l,r);
            int ok=0;
            for(int i=l;i<=r;i++)
                if(fb[i]){
                    ok = 1;
                    break;
                }
            printf("Case #%d: ",cas);
            printf(ok?"Yes\n":"No\n");
        }
        return 0;
    }

[hdoj 4786 Fibonacci Tree]: http://acm.hdu.edu.cn/showproblem.php?pid=4786