HDU 4786Fibonacci Tree(最小生成树)

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一个会写诗的程序员的博客

Spring Boot集成Security使用数据库用户角色权限用户名问题问题描述原因分析解决方案

sql语法手误。1?这地方写错了,应该是?1。这在敲代码的时候,手速一旦稍有不慎,就会导致前后顺序颠倒,而导致输入错误。这个虽然说是“低级错误”,但是错误搞起来...

1106
来自专栏码匠的流水账

聊聊spring cloud gateway的NettyConfiguration

本文主要研究下spring cloud gateway的NettyConfiguration

3971
来自专栏码匠的流水账

聊聊sentinel的FlowSlot

com/alibaba/csp/sentinel/slots/block/flow/FlowSlot.java

1561
来自专栏wym

HDU 6114 Chess

 题目:http://acm.hdu.edu.cn/showproblem.php?pid=6114

1012
来自专栏码匠的流水账

聊聊sentinel的NettyHttpCommandCenter

com/alibaba/csp/sentinel/transport/command/NettyHttpCommandCenter.java

1811
来自专栏菩提树下的杨过

asp中的md5/sha1/sha256算法收集

对于asp这种古董级的技术,这年头想找一些有用的资料已经不容易了,下面是一些常用的加密算法: md5 (将以下代码另存为md5.inc) <% Private ...

4029
来自专栏小灰灰

利用Crypto++实现RSA加密算法

之前做一个项目用到crypto++加密库,可以从官网下载对应的源码,其中有一个test.c文件,详细的演示了各种加密算法的使用方法,因此,在其基础上,我将ae...

4587
来自专栏web开发

移动端打印输出内容以及网络请求-vconsole.js

今天,无意间从别人那里得知一个很好的js插件--vconsole.min.js,可以实现在移动端打印输出内容以及查看网络请求。下面记录使用方式。 1、下载vco...

20710
来自专栏jeremy的技术点滴

python开发小技巧

3194
来自专栏码匠的流水账

聊聊jpa的batch操作的实现

hibernate-core-5.0.12.Final-sources.jar!/org/hibernate/internal/SessionImpl.java

2291

扫码关注云+社区

领取腾讯云代金券