HDU 4786（最小生成树 kruskal）
2024-09-08 16:16:47
题目链接： pid=4786" target="_blank">http://acm.hdu.edu.cn/showproblem.php?pid=4786
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?
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).
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
题意：
N个顶点,M条边。每条边或为白色或为黑色（ 1 or 0 ）。
问有没实用是斐波那契数的数目的白色边构成一棵生成树。
PS:
事实上说是并查集更靠谱一点的酱紫！
首先推断整个图是否是连通的，若不连通则直接输出No。
接下来首先仅讨论白边。不要黑边，看最多能增加多少条白边。使得不存在环。
这样我们得到了能增加白边的最大值max。（就是全部生成树里白边数量的最大值）。
接下来同理仅讨论黑边，这样我们能够得到可增加白边的最小值min。（也能够觉得是全部生成树中白边的最小值）。
然后我们仅仅要推断这两个值之间是否存在斐波那契数即可了。
代码例如以下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 100017;
struct node
{
int u, v;
int c;
} a[maxn];
int f[maxn], Fib[maxn];
int n, m;
int findd(int x)
{
return x==f[x] ? x : f[x]=findd(f[x]);
}
int kruskal(int sign)
{
int k = 0;
//sort(a,a+m,cmp);
for(int i = 0; i <= n; i++)
{
f[i] = i;
}
for(int i = 1; i <= m; i++)
{
if(a[i].c != sign)
{
int f1 = findd(a[i].u);
int f2 = findd(a[i].v);
if(f1 != f2)
{
f[f1] = f2;
k++;
}
}
}
return k;
}
void init()
{
Fib[0] = 1, Fib[1] = 2;
for(int i = 2; ; i++)
{
Fib[i] = Fib[i-1]+Fib[i-2];
if(Fib[i] > maxn)
break;
}
}
int main()
{
int t;
int cas = 0;
init();
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].c);
}
int ans = kruskal(2);
if(ans != n-1)//不能形成树
{
printf("Case #%d: No\n",++cas);
continue;
}
int maxx = kruskal(0);
int minn = n-1-kruskal(1);
int flag = 0;
for(int i = 0; ; i++)
{
if(Fib[i] >=minn && Fib[i]<=maxx)
{
flag = 1;
break;
}
if(Fib[i] > maxx)
{
break;
}
}
if(flag)
{
printf("Case #%d: Yes\n",++cas);
}
else
{
printf("Case #%d: No\n",++cas);
}
}
return 0;
}
最新文章
- UWP简单示例(一)：快速合成音乐MV
- Linux乱码问题解决方案
- Java集合运用技巧
- Java设计模式（二） 工厂方法模式
- Jquery ui autocomplete简单api
- 50道经典的JAVA编程题(31-35)
- 【原】Docker
- linux命令打开程序
- iOS UITextField 输入字数限制的实现
- Python 对Twitter中指定话题的Tweet基本元素的频谱分析
- TaintDroid：智能手机监控实时隐私信息流跟踪系统（三）
- redis运维的一些知识点
- C# 实现Html转JSON
- 20162311张之睿 Linux基础与Java开发环境实验报告
- vue-quasar-admin 一个包含通用权限控制的后台管理系统
- JUC (java.util.concurrent)
- 快速做ssh免密钥登陆
- 反射反射，程序员的快乐+反射案例：打印和Excel导出
- Benchmark Web App 性能瓶颈分析与性能测试工具的使用方法总结
- php in_array()优化