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
大致题意：有n个点，m条边，告诉你每条边是黑色0还是白色1。问你将这些点生成一棵树后，所用连接的边是的白色的数量能否是斐波那契数。
思路：n个点的生成树需要n-1条边，我们首先判断该图是否连通，如果不连通那么直接输出no。接下来，我们需要求出构成树时所能用的最多的白色边数Max和最少白色边数Min。我们可以先用白色的边去构图，用并查集来判断连接的点的数量n’,边数即为n’-1，那么最多白色边数Max=n’-1，然后我们再用黑色的边去构图，同理求出最多的黑色边数n”，那么最少需要的白色边数Min=n-1-n”（因为黑边加白边总边数为n-1）。白色边的数量所能取到的范围即[Min,Max]（我们可以这样想，因为最多取Max条白边，最少取Min条白边能构成树，所以每当我们减少一条白边时（不要动那些最少需要的白边）我们都能找到一条黑边使得图依旧连通），然后判断一下这个区间内是否有斐波那契数即可。
代码如下
#include<iostream> #include<algorithm> #include<string> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<cstring> using namespace std; const int maxn=100005; int pre[maxn]; int vis[100005]; int n,m; struct node { int x,y,c; } edge[maxn]; int find(int x) { int r=x; while (pre[r]!=r) r=pre[r]; int i=x; int j; while(i!=r) { j=pre[i]; pre[i]=r; i=j; } return r; } int solve(int k) { int num=0; for(int i=1;i<=n;i++) pre[i]=i; for(int i=1;i<=m;i++) { if(edge[i].c!=k)//k=1时取黑边构图 ，k=0时取白边构图，k=2时两个都取 { int f1=find(edge[i].x); int f2=find(edge[i].y); if(f1!=f2) { pre[f2]=f1; num++;//每新增一个点，边数加一 } } } return num; } int main() { int f[50];//存放斐波那契数 memset(vis,0,sizeof(vis)); vis[1]=vis[2]=f[1]=1; f[2]=2; for(int i=3;i<=24;i++) { f[i]=f[i-1]+f[i-2]; vis[f[i]]=1;//将斐波那契数标记为1 } int T; scanf("%d",&T); for(int t=1;t<=T;t++) { int flag=0; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].c); printf("Case #%d: ",t); if(solve(2)!=n-1)//首先判断是否连通 { printf("No\n"); continue; } int Min=n-1-solve(1);//求最少白边 int Max=solve(0);//求最多白边 for(int i=Min;i<=Max;i++) { if(vis[i]==1) { printf("Yes\n"); flag=1; break; } } if(!flag) printf("No\n"); } return 0; }