@natsumi 2017-01-13T02:00:04.000000Z 字数 4873 阅读 1400

# Fibonacci Tree 斐波那契树

Algorithms

HDU 4786

Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Source: 2013 Asia Chengdu Regional Contest

## 问题描述

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, ... )

## 输入

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).

## 输出

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.

## 示例

//输入：24 41 2 12 3 13 4 11 4 05 61 2 11 3 11 4 11 5 13 5 14 2 1
//输出Case #1: YesCase #2: No

## 解

//625MS 1772K  #include<stdio.h>  #include<string.h>  int f= {0,1};  int pre;  int n,m,k;  struct E  {      int u,v,c;  } edg;  void fib()  {      for(k=2;; k++)      {          f[k]=f[k-1]+f[k-2];          if(f[k]>100000)break;      }  }  void init()  {      for(int i=0; i<=n; i++)          pre[i]=i;  }  int find(int x)//路径压缩，否则很容易tle  {      int root=x;      while(root!=pre[root])      {          root=pre[root];      }      while(x!=root)      {          int temp=pre[x];          pre[x]=root;          x=temp;      }      return root;  }  int main()  {      int t,cas=1;      fib();      scanf("%d",&t);      while(t--)      {          int count=0;          scanf("%d%d",&n,&m);          for(int i=0; i<m; i++)              scanf("%d%d%d",&edg[i].u,&edg[i].v,&edg[i].c);          init();          printf("Case #%d: ",cas++);          for(int i=0; i<m; i++)//判断是不是连通图          {              int a=find(edg[i].u);              int b=find(edg[i].v);              if(a!=b)              {                  pre[a]=b;                  count++;              }          }          if(count!=n-1)          {              printf("No\n");              continue;          }          init();          int maxx=0,minn=0;          for(int i=0; i<m; i++)//求白边的最大数量              if(edg[i].c==1)              {                  int a=find(edg[i].u);                  int b=find(edg[i].v);                  if(a!=b){pre[a]=b,maxx++;}              }         init();         for(int i=0; i<m; i++)//求黑边最大数量              if(edg[i].c==0)              {                  int a=find(edg[i].u);                  int b=find(edg[i].v);                  if(a!=b){pre[a]=b,minn++;}              }          minn=n-1-minn;//求白边最小数量          int flag=0;          for(int i=1; i<k; i++)//在最大最小范围内，判断是否存在斐波那契数          {              if(f[i]>=minn&&f[i]<=maxx)              {                  flag=1;                  break;              }          }          if(flag)printf("Yes\n");          else printf("No\n");      }      return 0;  }

### 查并集和路径压缩

int pre;int find(int x){//查找根节点    int root=x;    //查并集    while ( pre[root]!= root )        root=pre[root];//返回根节点 r    int i=x , temp ;    //路径压缩    while( i != root ){        temp = pre[i]; // 在改变上级之前用临时变量temp记录下他的值         pre[i]= root ; //把上级改为根节点        i = temp;    }    return root ;}

#### 并查集的原理 #### 并查集的实现

int pre;这个数组，记录了每个大侠的上级是谁。大侠们从1或者0开始编号（依据题意而定），pre=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己，那说明他就是掌门人了，查找到此为止。也有孤家寡人自成一派的，比如欧阳锋，那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁？不认识！要想知道自己的掌门是谁，只能一级级查上去。 find这个函数就是找掌门用的，意义再清楚不过了（路径压缩算法先不论，后面再说）。

int pre;int find(int x){//查找我（x）的掌门    int root=x;//委托root去找掌门    while ( pre[root]!= root )//如果r的上级不是r自己（也就是说找到的大侠他不是掌门 = =）        root=pre[root];//root就接着找他的上级，直到找到掌门为止    return root;//掌门驾到~~~}

#### join函数

join函数，就是在两个点之间连一条线，这样一来，原先它们所在的两个板块的所有点就都可以互通了。这在图上很好办，画条线就行了。但我们现在是用并查集来描述武林中的状况的，一共只有一个pre[]数组，该如何实现呢？

void join(int x,int y){//我想让虚竹和周芷若做朋友    int fx=find(x),fy=find(y);//虚竹的老大是玄慈，芷若MM的老大是灭绝    if(fx!=fy)//玄慈和灭绝显然不是同一个人    pre[fx]=fy;//方丈只好委委屈屈地当了师太的手下啦}

#### 路径压缩 • 私有
• 公开
• 删除
{"ft_lang_label":"__label__zh","ft_lang_prob":0.75549203,"math_prob":0.9931223,"size":5355,"snap":"2019-43-2019-47","text_gpt3_token_len":3831,"char_repetition_ratio":0.0775556,"word_repetition_ratio":0.0061099795,"special_character_ratio":0.3006536,"punctuation_ratio":0.15662651,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99825597,"pos_list":[0,1,2,3,4,5,6,7,8],"im_url_duplicate_count":[null,1,null,1,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-11-22T13:49:37Z\",\"WARC-Record-ID\":\"<urn:uuid:a73b9054-3f5b-45d4-837b-5d4c7060930d>\",\"Content-Length\":\"137987\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:f3a4d069-bd4a-4bc6-8da6-cc9831971405>\",\"WARC-Concurrent-To\":\"<urn:uuid:5f1efdf1-7b6b-4caa-9064-7ca801d226b5>\",\"WARC-IP-Address\":\"115.29.168.58\",\"WARC-Target-URI\":\"https://www.zybuluo.com/natsumi/note/510326\",\"WARC-Payload-Digest\":\"sha1:PWBZVSYNU3DKYLOV5W3FZWNUGVIHDPBD\",\"WARC-Block-Digest\":\"sha1:TN4MQGY4V7M2MTZ6CHRDBF2VRVVBZOMX\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-47/CC-MAIN-2019-47_segments_1573496671260.30_warc_CC-MAIN-20191122115908-20191122143908-00273.warc.gz\"}"}