首页 > 代码库 > HDU 4786 Fibonacci Tree

HDU 4786 Fibonacci Tree

2024-07-04 11:51:54   233人阅读

点击打开链接

Fibonacci Tree

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 975    Accepted Submission(s): 289


Problem 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, ... )
 

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

Source
2013 Asia Chengdu Regional Contest

给你一个图，每条边有两种颜色黑色或者白色，让你判断存不存在一棵生成树，使得白边的数量为斐波那契数。
分别求出白边在生成树中的最大值和最小值，用生成树思想来做。当然如果图不是连通图的话，则肯定输出No。然后判断在这个最大最小之间存不存斐波那契数，如果存在则Yes，否则No。因为在这个区间内总能找到一条白边可以用黑边来代替。
//625MS	1772K
#include<stdio.h>
#include<string.h>
int f[107]= {0,1};
int pre[100007];
int n,m,k;
struct E
{
    int u,v,c;
} edg[100007];
void fib()
{
    for(k=2;; k++)
    {
        f[k]=f[k-1]+f[k-2];
        if(f[k]>100000)break;
    }
}
void init()
{
    for(int i=0; i<=n; i++)
        pre[i]=i;
}
int find(int x)//路径压缩，否则很容易tle
{
    int root=x;
    while(root!=pre[root])
    {
        root=pre[root];
    }
    while(x!=root)
    {
        int temp=pre[x];
        pre[x]=root;
        x=temp;
    }
    return root;
}

int main()
{
    int t,cas=1;
    fib();
    scanf("%d",&t);
    while(t--)
    {
        int count=0;
        scanf("%d%d",&n,&m);
        for(int i=0; i<m; i++)
            scanf("%d%d%d",&edg[i].u,&edg[i].v,&edg[i].c);
        init();
        printf("Case #%d: ",cas++);
        for(int i=0; i<m; i++)//判断是不是连通图
        {
            int a=find(edg[i].u);
            int b=find(edg[i].v);
            if(a!=b)
            {
                pre[a]=b;
                count++;
            }
        }
        if(count!=n-1)
        {
            printf("No\n");
            continue;
        }
        init();
        int maxx=0,minn=0;
        for(int i=0; i<m; i++)//求白边的最大数量
            if(edg[i].c==1)
            {
                int a=find(edg[i].u);
                int b=find(edg[i].v);
                if(a!=b){pre[a]=b,maxx++;}
            }
       init();
       for(int i=0; i<m; i++)//求黑边最大数量
            if(edg[i].c==0)
            {
                int a=find(edg[i].u);
                int b=find(edg[i].v);
                if(a!=b){pre[a]=b,minn++;}
            }
        minn=n-1-minn;//求白边最小数量
        int flag=0;
        for(int i=1; i<k; i++)//在最大最小范围内，判断是否存在斐波那契数
        {
            if(f[i]>=minn&&f[i]<=maxx)
            {
                flag=1;
                break;
            }
        }
        if(flag)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}



联系
我们