【HDU - 4786 】Fibonacci Tree （最小生成树变形，上下界贪心，tricks）

题干：

　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

Sample Output

Case #1: Yes
Case #2: No

题目大意：

一共n个点m条边，每条边有个权值1代表白边，0代表黑边，求能否建一个生成树，使得白边的数量是一个斐波那契数列

解题报告：

关于输出YesNo的问题，用界的方法去判定往往可以简化问题，比如这题我们虽然构造出这棵树来很难，但是判断是否存在却很简单，只需要看最少需要多少条白边和最多可以构造出多少条白边就可以了，然后中间所有白色边的数量的生成树就都可以构造出来了。

关于这一点好像没有很严谨的证明，但是也不难想通。因为可以抽象为白色边权为1，黑色边权为0，已知最小生成树为minn，最大生成树为maxx，那么我们一定可以通过+1（加白边减黑边），-1（减白边加黑边）的方式在不改变生成树性质的前提下将minn转移到maxx，所以这其中的任何一个权值都可以被凑出来。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
int n,m,tot;
int f[MAX],F[MAX],ff[MAX];
struct Edge {
	int u,v;
	int c;
} e[MAX];
bool cmp(Edge a,Edge b) {
	return a.c < b.c;
}
bool cmpp(Edge a,Edge b) {
	return a.c > b.c;
}
void add(int u,int v,int c) {
	e[++tot].u = u;e[tot].v = v;e[tot].c = c;
}
int getf(int v) {
	return f[v] == v ? v : f[v] = getf(f[v]);
}

void merge(int u,int v) {
	int t1 = getf(u),t2 = getf(v);
	f[t2] = t1;
}
bool check() {//返回1代表是一个连通图 
	int boss = getf(1);
	for(int i = 1; i<=n; i++) {
		if(getf(i) != boss) {
			return 0;
		}
	}
	return 1;
}
int fib[44],xuan[MAX];
bool isfib(int x) {
	for(int i = 1; i<=28; i++) {
		if(x == fib[i]) return 1;
	}
	return 0;
}
int cal() {
	int res = 0;
	for(int i = 1; i<=n; i++) f[i] = i;
	for(int i = 1; i<=m; i++) {
		if(getf(e[i].u) != getf(e[i].v)) {
			merge(e[i].u,e[i].v);
			if(e[i].c == 1) res++;
		}
	}
	return res;
}
int main()
{
	fib[1] = 1;fib[2] = 2;
	for(int i = 3; i<=40; i++) {
		fib[i] = fib[i-1] + fib[i-2];
	}
	int t,iCase=0;
	cin>>t;
	while(t--) {
		tot=0;
		scanf("%d%d",&n,&m);
		for(int i = 1; i<=n; i++) f[i] = i;
		for(int u,v,c,i = 1; i<=m; i++) scanf("%d%d%d",&u,&v,&c),add(u,v,c),xuan[i] = 0;
		printf("Case #%d: ",++iCase);
		for(int i = 1; i<=m; i++) {
			merge(e[i].u,e[i].v);
		}
		if(check() == 0) printf("No\n");
		else {
			sort(e+1,e+m+1,cmp);
			int flag = 0,low = cal();
			sort(e+1,e+m+1,cmpp);
			int up = cal();
			for(int i = 1; i<=28; i++) {
				if(fib[i] >= low && fib[i] <= up) flag = 1;
			}
			if(flag == 1) printf("Yes\n");
			else printf("No\n");
		}
	} 
	return 0 ;
}