链接：http://acm.hdu.edu.cn/showproblem.php?pid=4786
题意：给出n个点，m条边，和边的信息。
边有两种颜色，白色和黑色。现要求构造一个生成树。看是否能满足白边的数量是斐波那契数。
这道题比赛的时候，小白想到了一种方法：按边颜色排序后，先用白边优先建树，求出最大白边最大个数maxm，再用黑边优先建树，求出白边最小个数minm。看这两个范围内是否存在斐波那契数。
听上去感觉还挺有道理，可是不知道怎么证明正确性，后来想想，生成树构造完之后。再加入随意一条边都会产生回路。而产生回路之后就有边会被替换，而minm是最少的白边数，也就是minm个白边是不会被换掉的。maxm同理，所以中间的回路替换掉边总能保证用白边替换黑边，或者黑边替换白边。所以能够这么做。
我信心满满的開始敲。然后WA了。。
由于我写完cmp函数后忘记写sort了，并且还过了例子。改过之后交一发。还是WA。后来发现数组开了110。。。并且提示是WA不是RE
另外，这道题假设不进行路径压缩，会超时
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 110000
#define eps 1e-7
#define INF 0x7FFFFFFF
#define seed 131
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 struct node{
int u,v,col;
}edge[MAXN];
int father[MAXN],fi[90];
int n,m,flag;
bool cmp(node x,node y){
return x.col>y.col;
}
int find(int x){
int t = x;
while(father[t]!=t){
t = father[t];
}
int k = x;
while(k!=t){
int temp = father[k];
father[k] = t;
k = temp;
}
return t;
}
void solve(){
int i,j=0;
int flag2 = 0;
int minm,maxm;
minm = maxm = 0;
sort(edge,edge+m,cmp);
for(i=0;i<m;i++){
int a = find(edge[i].u);
int b = find(edge[i].v);
if(a!=b){
if(edge[i].col==1) maxm++;
father[a] = b;
j++;
if(j>=n-1){
flag2 = 1;
break;
}
}
}
if(flag2==0){
return ;
}
for(i=1;i<=n;i++){
father[i] = i;
}
j = 0;
for(i=m-1;i>=0;i--){
int a = find(edge[i].u);
int b = find(edge[i].v);
if(a!=b){
if(edge[i].col==1) minm++;
father[a] = b;
j++;
if(j>=n-1) break;
}
}
//cout<<minm<<" "<<maxm<<endl;
for(i=1;i<45;i++){
if(fi[i]>=minm&&fi[i]<=maxm)
{
flag = 1;
break;
}
}
}
int main(){
int i,j,k=1,t;
int a,b,c;
fi[1] = 1;
fi[2] = 2;
for(i=3;i<45;i++){
fi[i] = fi[i-1] + fi[i-2];
//cout<<fi[i]<<" "<<i<<" "<<endl;
}
scanf("%d",&t);
while(t--){
flag = 0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) father[i] = i;
for(i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
edge[i].u = a;
edge[i].v = b;
edge[i].col = c;
}
solve();
if(flag) printf("Case #%d: Yes\n",k++);
else printf("Case #%d: No\n",k++);
}
return 0;
}