本文主要是介绍Fibonacci Tree HDU - 4786 (生成树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Fibonacci Tree
题目链接：HDU - 4786
题意：给出一个图，每条边的权值要么是0，要么是1，问能否构成一棵生成树，使得这棵树的边权和为斐波那契数；
思路：记图的最大生成树和最小生成树的边权和分别为max, min，那么，一定可以构造出合法的生成树，使得其边权和在区间[min, max]；这是个值得思考的地方；
当我们得到一个最小生成树后，想要向最大生成树转换时，必定是通过换边解决，而图中的边权为1 or 0，所以有四种情况：1->1， 1->0， 0->1， 0->0；这四种情况对于边权和的贡献分别为0, -1, 1, 0；所以由min->max的过程中每一个值都必定有对应的生成树结构出现；
所以只需判断区间[min, max]之间有没有斐波那契数就可以了，注意还要判断图是否连通；
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int N, M;
int pre[maxn];
int find(int x){return x==pre[x]?pre[x]:pre[x]=find(pre[x]);
}
bool Union(int x, int y){int fx=find(x), fy=find(y);if(fx==fy) return false;pre[fx]=fy;return true;
}
struct node{int u, v, w;
}edge[maxn];
void init(){for(int i=0; i<=N; i++){pre[i]=i;}
}
bool cmp1(node a, node b){return a.w<b.w;
}
bool cmp2(node a, node b){return a.w>b.w;
}
int Kruskal(){init();int ret=0, cnt=0;for(int i=0; i<M; i++){if(Union(edge[i].u, edge[i].v)){ret+=edge[i].w;cnt++;}if(cnt==N-1) break;}if(cnt<N-1) return 0;return ret;
}
bool fib[maxn];
void get_fib(){memset(fib, false, sizeof(fib));fib[0]=false;fib[1]=true;fib[2]=true;int cnt=3, f1=1, f2=2;while(1){int t=f1+f2;f1=f2, f2=t;if(t>=maxn) break;fib[t]=true;}
}
int main(){int T, cas=0;scanf("%d", &T);get_fib();while(T--){scanf("%d%d", &N, &M);for(int i=0; i<M; i++){scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);}sort(edge, edge+M, cmp1);int minn=Kruskal();sort(edge, edge+M, cmp2);int maxn=Kruskal();int flag=0;for(int i=minn; i<=maxn; i++){if(fib[i]){flag=1;break;}}printf("Case #%d: ", ++cas);if(flag) printf("Yes\n");else printf("No\n");}return 0;
}
这篇关于Fibonacci Tree HDU - 4786 (生成树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
