HDU 4786Fibonacci Tree(最小生成树)

2018-06-17 21:12:39来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:游戏服务器设计之NPC系统

下一篇:次小生成树