题目链接<-点击
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
没想到这题居然是区域赛的题，应该是一个签到题吧
题目大意，就是有两种颜色的边，黑边和白边，你要把所有的点连接起来，并使得你用的白边树是斐波那契数列中的一个数。
思路： 先打表斐波那契，然后求出来最大生成树（尽可能使用白边）和最小生成树（尽可能使用黑边），若最大值和最小值之间有斐波那契数列中的一个数，就正确，否则就没有。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=1000000+100; int vis[maxn],post[maxn]; int pre[maxn]; int n,m; struct node { int from,to,val; }road[maxn]; int cmp(node aa,node bb) { return aa.val>bb.val; } int cmp1(node aa,node bb) { return aa.val<bb.val; } int findd(int x) { int r=x; while(r!=pre[r]) r=pre[r]; int i=x,j; while(i!=r) { j=pre[i]; pre[i]=r; i=j; } return r; } int zyz() { int i; for(i=0;i<=n;i++) { pre[i]=i; } sort(road+1,road+1+m,cmp); int ans=0; int aaaa=1; for(i=1;i<=m;i++) { int tx=findd(road[i].from); int ty=findd(road[i].to); if(tx!=ty) { pre[ty]=tx; ans+=road[i].val; aaaa++; } } if(aaaa<n) return -1; else return ans; } int zhang() { int i; for(i=0;i<=n;i++) { pre[i]=i; } sort(road+1,road+1+m,cmp1); int ans=0; int aaaa=1; for(i=1;i<=m;i++) { int tx=findd(road[i].from); int ty=findd(road[i].to); if(tx!=ty) { pre[ty]=tx; ans+=road[i].val; aaaa++; } } if(aaaa<n)//注意啊！！！！wa了四发，这里以前从来没注意过！！！ return -1; else return ans; } int main () { int t; memset(post,0,sizeof(post)); memset(vis,0,sizeof(vis)); vis[1]=1; vis[2]=1; post[0]=1; post[1]=2; int cnt=1; while(post[cnt]<maxn) { post[++cnt]=post[cnt-1]+post[cnt-2]; if(post[cnt]<maxn) vis[post[cnt]]=1; } scanf("%d",&t); int kk; for(kk=1;kk<=t;kk++) { scanf("%d%d",&n,&m); int i; for(i=1;i<=m;i++) { scanf("%d%d%d",&road[i].from,&road[i].to,&road[i].val); } int ed=zyz(); int st=zhang(); int flag=0; if(ed==-1||st==-1) { printf("Case #%d: No\n",kk); continue; } for(i=st;i<=ed;i++) { if(vis[i]) { flag=1; break; } } if(flag) printf("Case #%d: Yes\n",kk); else printf("Case #%d: No\n",kk); } }