hdoj 4786 Fibonacci Tree【并查集+最小生成树(kruskal算法)】
2024-08-23 13:10:08
Fibonacci Tree
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2915 Accepted Submission(s):
931
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, ... )
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).
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.
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
题意:两条边之间1代表是白边,0代表是黑边,求是否存在一棵最小树使它的边中有Fibonacci 数列( 1, 2, 3, 5, 8, ... )中
数条白边(最小树中边可有白边可有黑边)
题解:利用打表将Fibonacci 数列存在数组fib[]中先将边按照由白到黑排序求出生成一棵最小树最多需要白边多少条max;再将边按
照有黑到白排序求出生成一棵最小树最少需要白边多少条min,如果存在Fibonacci 数列中一个数使min<=fib[i]<=max则输
出yes否则输出no(如果无法生成一棵树也输出no)
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAX 100010
using namespace std;
struct recode
{
int beg;
int end;
int bian;
}s[MAX];
bool cmp1(recode a,recode b)
{
return a.bian>b.bian;
}
bool cmp2(recode a,recode b)
{
return a.bian<b.bian;
}
int set[MAX];
int fib[MAX];
void biao()
{
int i,j;
fib[1]=1;
fib[2]=2;
for(i=3;fib[i]<MAX;i++)
{
fib[i]=fib[i-1]+fib[i-2];
}
}
int find(int fa)
{
int t;
int ch=fa;
while(fa!=set[fa])
fa=set[fa];
while(ch!=fa)
{
t=set[ch];
set[ch]=fa;
ch=t;
}
return fa;
}
void mix(int x,int y)
{
int fx,fy;
fx=find(x);
fy=find(y);
if(fx!=fy)
set[fx]=fy;
}
int main()
{
int n,m,j,i,t;
scanf("%d",&t);
int k=1;
biao();
while(t--)
{
scanf("%d%d",&n,&m);
int sum=0;
for(i=0;i<m;i++)
scanf("%d%d%d",&s[i].beg,&s[i].end,&s[i].bian);
int min=0,max=0;
for(i=0;i<=n;i++)
set[i]=i;
sort(s,s+m,cmp1);
for(i=0;i<m;i++)
{
//printf("%d %d # ",s[i].beg,s[i].end);
if(find(s[i].beg)!=find(s[i].end))
{
mix(s[i].beg,s[i].end);
if(s[i].bian==1)
max++;
}
}
// printf("\n");
// printf("%d \n",max);
for(i=0;i<=n;i++)
set[i]=i;
sort(s,s+m,cmp2);
for(i=0;i<m;i++)
{
// printf("%d %d # ",s[i].beg,s[i].end);
if(find(s[i].beg)!=find(s[i].end))
{
mix(s[i].beg,s[i].end);
if(s[i].bian==1)
min++;
}
}
// printf("\n");
// printf("%d \n",min);
printf("Case #%d: ",k++);
int wrong=0;
int mis=0;
for(i=1;i<=n;i++)
{
if(set[i]==i)
wrong++;
if(wrong>1)
{
mis=1;
break;
}
}
if(mis)
{
printf("No\n");
continue;
}
int ok=0;
for(i=1;fib[i]<=m;i++)
{
if(fib[i]>=min&&fib[i]<=max)
{
printf("Yes\n");
ok=1;
break;
}
}
if(!ok)
printf("No\n");
}
return 0;
}
最新文章
- web前端书籍
- sqlserver 锁与阻塞
- 第三节 构造一个简单的Linux系统MenuOS——20135203齐岳
- android studio 修改成自己jks(keystore)签名文件
- PHP-PCRE正则表达式函数
- NoSQL数据库有哪些
- Java 理论和实践: 了解泛型
- [树莓派(raspberry pi)] 02、PI3安装openCV开发环境做图像识别(详细版)
- Ansible学习总结(1)
- RF无线射频电路设计干货分享
- JAVA 注解和反射
- .NET CORE 设置cookie以及获取cookie
- Discuz网警过滤关键词库
- Github上Laravel开源排行榜Star数61-90名
- Select模式和超时
- jQuery1.11源码分析(2)-----Sizzle源码中的正则表达式[原创]
- 轻量级分布式 RPC 框架(转)
- 虚拟机和Docker的异同
- 通过maven自动修改idea的compiler
- VS2010 + QT 5 +open inventor 环境配置