首页 > 代码库 > hdoj 4786 Fibonacci Tree 【生成树+想法】
hdoj 4786 Fibonacci Tree 【生成树+想法】
题目:hdoj 4786 Fibonacci Tree
题意:给出 n 个点 m 条边的图,边只有两种颜色,白色和黑色,让你判断能不能让一个生成树中白边的个数为斐波那契数。
分析:这是个想法题目,前提是知道生成树的定义:生成树必须是所有点都在树中
那么既然要是斐波那契数,我只要把白色边的最大个数和最小个数求出来,如果这个范围内有斐波那契数的话,那么就满足条件。
当然这样求的前提条件是期间的所有的生成树都是满足条件的。即都是满足能够生成树的。
ok,AC代码:
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #include<stack> #define MAXN 100005 using namespace std; struct node { int x,y,val; } a[MAXN]; int fb[MAXN]; int father[MAXN]; void isit() { memset(fb,0,sizeof(fb)); int a = 1,b = 1; fb[1] = 1; for(int c = a+b;c<=MAXN; c=b+a) { fb[c] = 1; a = b; b = c; } } bool cmp(node a,node b) { return a.val<b.val; } int Find(int u) { if (father[u]==u) return u; return father[u]=Find(father[u]); } int Yougth(int n,int m,int x) { for(int i=1;i<=n;i++) father[i] = i; int ans = 0; int start = m-1; if(x==1) start = 0; for(int i=start;i>=0 && i<m ;i+=x) { int s = Find(a[i].x) ,t = Find(a[i].y); //printf("%d %d %d %d\n",father[a[i].x],father[a[i].y],a[i].x,t); if(s == t) continue; father[s]=t; ans+=a[i].val; } int tmp = Find(1); for(int i=2;i<=n;i++) if(Find(i)!=tmp) return 10; return ans; } int main() { //freopen("Input.txt","r",stdin); int T; isit(); scanf("%d",&T); for(int cas=1;cas<=T;cas++) { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].val); sort(a,a+m,cmp); int r = Yougth(n,m,-1),l = Yougth(n,m,1); //printf("%d %d\n",l,r); int ok=0; for(int i=l;i<=r;i++) if(fb[i]){ ok = 1; break; } printf("Case #%d: ",cas); printf(ok?"Yes\n":"No\n"); } return 0; }
hdoj 4786 Fibonacci Tree 【生成树+想法】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。