HDU 4786(최소 생 성 트 리 kruskal)
6063 단어 최소 생 성 트 리
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 <= 10
5) and M(0 <= M <= 10
5).
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
题意:
N个顶点,M条边,每条边或为白色或为黑色( 1 or 0 ),
问有没有用是斐波那契数的数目的白色边构成一棵生成树。
PS:
其实说是并查集更靠谱一点的酱紫!
首先判断整个图是否是连通的,若不连通则直接输出No。
接下来首先仅讨论白边,不要黑边,看最多能加入多少条白边,使得不存在环。这样我们得到了能加入白边的最大值max。(就是所有生成树里白边数量的最大值)。
接下来同理仅讨论黑边,这样我们可以得到可加入白边的最小值min,(也可以认为是所有生成树中白边的最小值)。
然后我们只要判断这两个值之间是否存在斐波那契数就行了。
代码如下:
#include
#include
#include
#include
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
",++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
",++cas);
}
else
{
printf("Case #%d: No
",++cas);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
7 - 10 도로 촌 촌 통 (30 분) 자바 버 전이것 이 바로 가장 짧 은 길 입 니 다. 순 서 를 정 하고 start 와 end 를 찾 으 면 됩 니 다. c++ 로 하면 10 분 이면 끝 낼 수 있 을 것 같 습 니 다. 하지만 이번 학기 에 자바 를 배 우...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.