程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4786 Fibonacci Tree(生成樹，YY亂搞)

HDU 4786 Fibonacci Tree(生成樹，YY亂搞)

編輯：C++入門知識

HDU 4786 Fibonacci Tree(生成樹，YY亂搞)

Fibonacci Tree
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1733    Accepted Submission(s): 543

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⁵) and M(0 <= M <= 10⁵).
　　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

Sample Output

Case #1: Yes
Case #2: No

Source 2013 Asia Chengdu Regional Contest
題意：給出一個無向圖，每條邊都已染色（黑/白），問是否存在生成樹，該生成樹的白色邊的數量是正的fibonacci數。分析：所給數據中黑邊為0，白邊為1，那麼生成樹的白邊數量即為生成樹的權和。然後YY了一個做法：求其最小和最大生成樹，如果在這個范圍內存在fibonacci數則存在。靠譜的證明方法一直沒想出來，這裡隨便解釋下：對於任意一顆非最大生成樹，一定可以取一條白邊換一條黑邊使其仍然是一顆樹。

/*
 *
 * Author : fcbruce
 *
 * Time : Mon 06 Oct 2014 01:06:30 PM CST
 *
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10

#ifdef _WIN32
  #define lld %I64d
#else
  #define lld %lld
#endif

#define maxm 100007
#define maxn 100007

using namespace std;

int fib[maxn];
struct _edge
{
  int u,v,w;
  bool operator < (const _edge &_)const
  {
    return w<_.w;
  }
}edge[maxm];

int pre[maxn];

int root(int x)
{
  if (x==pre[x]) return x;
  return pre[x]=root(pre[x]);
}

bool same(int x,int y)
{
  return root(x)==root(y);
}

void _merge(itn x,int y)
{
  pre[root(x)]=root(y);
}

int cnt,fib_cnt;

int main()
{
#ifdef FCBRUCE
  freopen(/home/fcbruce/code/t,r,stdin);
#endif // FCBRUCE
  
  int T_T,__=0;
  scanf(%d
,&T_T);

  fib[0]=1;
  fib[1]=1;
  fib_cnt=2;
  for (int i=2;;i++)
  {
    fib[i]=fib[i-1]+fib[i-2];
    fib_cnt++;
    if (fib[i]>100000) break;
  }

  while (T_T--)
  {
    printf(Case #%d: ,++__);
    int n,m;
    scanf(%d%d,&n,&m);
    for (int i=1;i<=n;i++) pre[i]=i;
    cnt=n;
    for (int i=0,u,v,w;i=0;i--)
    {
      u=edge[i].u;v=edge[i].v;w=edge[i].w;
      if (!same(u,v))
      {
        _merge(u,v);
        MAX+=w;
        cnt--;
        if (cnt==1) break;
      }
    }

    int idmin=lower_bound(fib,fib+fib_cnt,MIN)-fib;
    int idmax=lower_bound(fib,fib+fib_cnt,MAX)-fib;

    if (fib[idmin]!=MIN && fib[idmax]!=MAX && idmin==idmax)
      puts(No);
    else
      puts(Yes);
    
  }



  return 0;
}