首页 > 代码库 > Fibonacci Tree

Fibonacci Tree

2024-07-18 05:22:07   229人阅读

hdu4786:http://acm.hdu.edu.cn/showproblem.php?pid=4786

题意：给你一个无向图，然后其中有的边是白色的有的边是黑色的。然后问你是否存在一棵生成树，在这课生成树上白色边的数量是一个斐波那契数。

题解：完全没有那样的思想，一道现场水题，就是不会啊，实力太弱 啊。注定打铁啊。这一题是这样的，采用极端思维：就是分别用白色和黑色优先的边去求生成树，得到一个白色数量的区间。这里需要理解的是，白色边的数目，可以在这个区间内变化。也就是构成生成树的白色边的数量在这个区间内，如果这个区间内的数没有一个是斐波那契数，那么就不可能了。同时处理出1e5以内的斐波那契数。

  1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 #include<iostream>  5 using namespace std;  6 const int N=2e5+10;  7 int fa[N],f[40],vis[N];  8 int n,m,u,v,w;  9 struct Node{ 10    int u,v; 11    int w; 12    bool operator<(const Node a)const { 13     return w>a.w; 14     } 15 }edge1[N]; 16 struct Node1{ 17    int u,v; 18    int w; 19    bool operator<(const Node1 a)const { 20     return w<a.w; 21     } 22 }edge2[N]; 23 void init(){ 24    for(int i=1;i<=n;i++) 25     fa[i]=i; 26 } 27 int Find(int x){ 28     int s; 29     for(s=x;s!=fa[s];s=fa[s]); 30     while(x!=s){ 31         int temp=fa[x]; 32           fa[x]=s; 33           x=temp; 34     } 35    return s; 36 } 37 int solve1(){//黑色优先 38    int ct=0,num=0; 39    for(int i=1;i<=m;i++){ 40       int u=Find(edge1[i].u); 41       int v=Find(edge1[i].v); 42       if(u!=v){ 43         fa[u]=v; 44         if(edge1[i].w==1) 45             ct++; 46         num++; 47       } 48      if(num==n-1) 49         return ct; 50    } 51    return 0; 52 } 53 int solve2(){ 54     init(); 55    int ct=0,num=0; 56    for(int i=1;i<=m;i++){ 57       int u=Find(edge2[i].u); 58       int v=Find(edge2[i].v); 59       if(u!=v){ 60         fa[u]=v; 61         if(edge2[i].w==1) 62             ct++; 63         num++; 64       } 65      if(num==n-1) 66         return ct; 67    } 68    return 0; 69 } 70 int main(){ 71     int T,tt=1; 72     scanf("%d",&T); 73    while(T--){ 74      scanf("%d%d",&n,&m); 75       init(); 76       for(int i=1;i<=m;i++){ 77           scanf("%d %d %d",&u,&v,&w); 78         edge1[i].u=u;edge1[i].v=v;edge1[i].w=w; 79         edge2[i].u=u;edge2[i].v=v;edge2[i].w=w; 80       } 81       sort(edge1+1,edge1+m+1); 82       sort(edge2+1,edge2+m+1); 83       int ll=solve2(); 84       int rr=solve1(); 85       memset(f,0,sizeof(f)); 86       memset(vis,0,sizeof(vis)); 87       f[0]=0;f[1]=1; 88       for(int i=2;i<=21;i++){ 89          f[i]=f[i-1]+f[i-2]; 90          vis[f[i]]=1; 91       } 92       bool flag=false; 93       for(int i=ll;i<=rr;i++) 94       if(vis[i]){ 95         flag=true; 96         break; 97       } 98       if(flag)printf("Case #%d: Yes\n",tt++); 99       else100         printf("Case #%d: No\n",tt++);101    }102 }
View Code

 


联系
我们