首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU 4786Fibonacci Tree(最小生成树)

HDU 4786Fibonacci Tree(最小生成树)

作者头像
attack
发布2018-04-10 18:35:05
1K0
发布2018-04-10 18:35:05
举报

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

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;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-02-22 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档