http://acm.hdu.edu.cn/showproblem.php?pid=4786
Fibonacci Tree
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 49 Accepted Submission(s): 26
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, ... )
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, ... )
思路：想法题，感觉成都的题想法很重要啊。。。
首先判断整个图是否连通，若不连通直接输出No，都不连通了当然生成树就无从说起了嘛。
接下来仅讨论白边，黑边不看，看最多能加入多少条白边，使得不存在环。这样我们得到了能加入白边的最大值max。（就是所有生成树里白边数量的最大值）。
接下来同理仅讨论黑边，这样我们可以得到可加入白边的最小值min，（也可以认为是所有生成树中白边的最小值）。
然后我们只要判断这两个值之间是否存在斐波那契数就行了。
为什么呢？这里说明一下，
我们等于是要证明对于所有在min和max之间的白边数我们都能够达到。
考虑从最小的min开始，我总可以找到一条黑边，使得将它去掉在补上一条白边保持图联通。为什么呢，如果在某一个状态（设白边数为x）下，不存在一条黑边可以被白边代替，那么现在我们把所有黑边去掉，剩下x条白边，那我们知道，x一定等于max，因为若x<max，那么我们在算max的那个步骤中，现将这x条白边加入，还可以在加入max-x条白边使得不存在环，那么这与没有一条黑边可以被白边代替矛盾，所以这就证明了从min到max我都可以达到。
说的有点乱，感觉自己想想还是能能明白的吧。下面就是代码了，很好理解应该。
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxn 100010
using namespace std;
int f[maxn],febo[50];
int n,m;
struct edge
{
int u,v,c;
}e[maxn];
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
int solve(int col)
{
int num=0;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)
{
if(e[i].c!=col)
{
int x=find(e[i].u),y=find(e[i].v);
if(x!=y)
{
f[x]=y;
num++;
}
}
}
return num;
}
int main()
{
freopen("dd.txt","r",stdin);
febo[0]=1,febo[1]=2;
int num;
for(num=2;;num++)
{
febo[num]=febo[num-1]+febo[num-2];
if(febo[num]>100000)
break;
}
int ncase,T=0;
scanf("%d",&ncase);
while(ncase--)
{
printf("Case #%d: ",++T);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c);
int tmp,mi,ma,tru=0;
tmp=solve(2);
if(tmp!=n-1)
{
printf("No\n");
continue;
}
ma=solve(0);
mi=n-1-solve(1);
for(int i=0;i<num;i++)
{
if(febo[i]>=mi&&febo[i]<=ma)
{
tru=1;
break;
}
}
if(tru)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}