# HDU 4786Fibonacci Tree(最小生成树)

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

Source

2013 Asia Chengdu Regional Contest

Recommend

We have carefully selected several similar problems for you:  6263 6262 6261 6260 6259

```#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10,INF=1e9+10;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
}
{
char c=nc();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
return x*f;
}
struct node
{
int u,v,w;
}edge[MAXN];
int num=1;
inline void AddEdge(int x,int y,int z)
{
edge[num].u=x;
edge[num].v=y;
edge[num].w=z;num++;
}
int N,M;
int fib[MAXN];
int fa[MAXN];
int comp1(const node &a,const node &b){return a.w<b.w;}
int comp2(const node &a,const node &b){return a.w>b.w;}
int find(int x)
{
if(fa[x]==x) return fa[x];
else return fa[x]=find(fa[x]);
}
void unionn(int x,int y)
{
int fx=find(x);
int fy=find(y);
fa[fx]=fy;
}
int Kruskal(int opt)
{
if(opt==1) sort(edge+1,edge+num,comp1);
else sort(edge+1,edge+num,comp2);
int ans=0,tot=0;
for(int i=1;i<=num-1;i++)
{
int x=edge[i].u,y=edge[i].v,z=edge[i].w;
if(find(x) == find(y)) continue;
unionn(x,y);
tot++;
ans=ans+z;
if(tot==N-1) return ans;
}
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
fib[1]=1;fib[2]=2;
for(int i=3;i<=66;i++) fib[i]=fib[i-1]+fib[i-2];
int cnt=0;
while(Test--)
{
for(int i=1;i<=N;i++) fa[i]=i;
for(int i=1;i<=M;i++)
{
}
int minn=Kruskal(1);
for(int i=1;i<=N;i++) fa[i]=i;
int maxx=Kruskal(2);
bool flag=0;
for(int i=1;i<=66;i++)
if(minn <= fib[i] && fib[i] <= maxx)
{printf("Case #%d: Yes\n",++cnt);flag=1;break;}
if(flag==0) printf("Case #%d: No\n",++cnt);
}
return 0;
}```

1811 篇文章120 人订阅

0 条评论

## 相关文章

### Spring Boot集成Security使用数据库用户角色权限用户名问题问题描述原因分析解决方案

sql语法手误。1?这地方写错了，应该是?1。这在敲代码的时候，手速一旦稍有不慎，就会导致前后顺序颠倒，而导致输入错误。这个虽然说是“低级错误”，但是错误搞起来...

1106

3971

### 聊聊sentinel的FlowSlot

com/alibaba/csp/sentinel/slots/block/flow/FlowSlot.java

1561

### HDU 6114 Chess

题目：http://acm.hdu.edu.cn/showproblem.php?pid=6114

1012

### 聊聊sentinel的NettyHttpCommandCenter

com/alibaba/csp/sentinel/transport/command/NettyHttpCommandCenter.java

1811

4029

4587

20710

3194

### 聊聊jpa的batch操作的实现

hibernate-core-5.0.12.Final-sources.jar!/org/hibernate/internal/SessionImpl.java

2291