HDU 4786Fibonacci Tree(最小生成树)

怼烎@ 2022-04-10 11:45 141阅读 0赞

**Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 5934 Accepted Submission(s): 1845**

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 <= 10 5) and M(0 <= M <= 10 5).  
　　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 ][2013 Asia Chengdu Regional Contest]

Recommend

We have carefully selected several similar problems for you: [6263][] [6262][] [6261][] [6260][] [6259][]

**和昨天ysy讲的那道题差不多**

**而且这道题在题目中直接给提示了——》黑边为0，白边为1**

**这样的话我们做一个最小生成树和一个最大生成树**

**如果在这两个值的范围内有斐波那契数，就说明满足条件**

**简单证明：**  
**对于最小生成树来说，任意删除一条边，并加入一条没有出现过的边，这样的话权值至多加1，边界为最大生成树**

#include<cstdio>
    #include<algorithm>
    using namespace std;
    const int MAXN=1e6+10,INF=1e9+10;
    inline char nc()
    {
        static char buf[MAXN],*p1=buf,*p2=buf;
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
    }
    inline int read()
    {
        char c=nc();int x=0,f=1;
        while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=nc();}
        while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
        return x*f;
    }
    struct node
    {
        int u,v,w;
    }edge[MAXN];
    int num=1;
    inline void AddEdge(int x,int y,int z)
    {
        edge[num].u=x;
        edge[num].v=y;
        edge[num].w=z;num++;
    }
    int N,M;
    int fib[MAXN];
    int fa[MAXN];
    int comp1(const node &a,const node &b){
         return a.w<b.w;}
    int comp2(const node &a,const node &b){
         return a.w>b.w;}
    int find(int x)
    {
        if(fa[x]==x) return fa[x];
        else return fa[x]=find(fa[x]);
    }
    void unionn(int x,int y)
    {
        int fx=find(x);
        int fy=find(y);
        fa[fx]=fy;
    }
    int Kruskal(int opt)
    {
        if(opt==1) sort(edge+1,edge+num,comp1);
        else sort(edge+1,edge+num,comp2);
        int ans=0,tot=0;
        for(int i=1;i<=num-1;i++)
        {
            int x=edge[i].u,y=edge[i].v,z=edge[i].w;
            if(find(x) == find(y)) continue;
            unionn(x,y);
            tot++;
            ans=ans+z;
            if(tot==N-1) return ans;
        }
    }
    int main()
    {
        #ifdef WIN32
        freopen("a.in","r",stdin);
        #else
        #endif
        int Test=read();
        fib[1]=1;fib[2]=2;
        for(int i=3;i<=66;i++) fib[i]=fib[i-1]+fib[i-2];
         int cnt=0;
         while(Test--)
        {
            N=read(),M=read();num=1;
            for(int i=1;i<=N;i++) fa[i]=i;
            for(int i=1;i<=M;i++)
            {
                int x=read(),y=read(),z=read();
                AddEdge(x,y,z);
                AddEdge(y,x,z);
            }
            int minn=Kruskal(1);
            for(int i=1;i<=N;i++) fa[i]=i;
            int maxx=Kruskal(2);
            bool flag=0;
            for(int i=1;i<=66;i++)
                if(minn <= fib[i] && fib[i] <= maxx) 
                    {printf("Case #%d: Yes\n",++cnt);flag=1;break;}
            if(flag==0) printf("Case #%d: No\n",++cnt);
        }
        return 0;
    }

[2013 Asia Chengdu Regional Contest]: http://acm.hdu.edu.cn/search.php?field=problem&key=2013+Asia+Chengdu+Regional+Contest+&source=1&searchmode=source
[6263]: http://acm.hdu.edu.cn/showproblem.php?pid=6263
[6262]: http://acm.hdu.edu.cn/showproblem.php?pid=6262
[6261]: http://acm.hdu.edu.cn/showproblem.php?pid=6261
[6260]: http://acm.hdu.edu.cn/showproblem.php?pid=6260
[6259]: http://acm.hdu.edu.cn/showproblem.php?pid=6259