首页 > 代码库 > hdu 4786 Fibonacci Tree (最小、最大生成树)
hdu 4786 Fibonacci Tree (最小、最大生成树)
题意：
N个点，M条边。每条边连接两个点u,v，且有一个权值c，c非零即一。
问能否将N个点形成一个生成树，并且这棵树的边权值和是一个fibonacii数。 （fibonacii数=1,2,3,5,8 .... ）
思路：
若可以生成一棵树。则有最小生成树和最大生成树。假设已经生成了最小MST P 和最大MST Q。
将P更换一条边可以得到另一棵生成树，边权和不是和P相等就是比P的边权和大1。（因为边值非零即一）。同理搞下去....一定可以得到Q。
所以P的边权和到Q的边权和之间的所有值都能得到。故判断之间是否存在fibonacii数即可。
代码：
struct node{ int u,v,c;}edge[100005];bool cmp(node a,node b){ return a.c<b.c;}int fa[100005];int T,n,m;int findFa(int x){ return fa[x]==x?x:fa[x]=findFa(fa[x]);}int kruskal1(){ rep(i,1,n) fa[i]=i; int res=0; rep(i,1,m){ int fx=findFa(edge[i].u); int fy=findFa(edge[i].v); if(fx!=fy){ fa[fx]=fy; res+=edge[i].c; } } int tx=findFa(1); rep(i,2,n) if(findFa(i)!=tx) return -1; return res;}int kruskal2(){ rep(i,1,n) fa[i]=i; int res=0; rep2(i,m,1){ int fx=findFa(edge[i].u); int fy=findFa(edge[i].v); if(fx!=fy){ fa[fx]=fy; res+=edge[i].c; } } int tx=findFa(1); rep(i,2,n) if(findFa(i)!=tx) return -1; return res;}bool isFibo[100005];void FiboD(){ mem(isFibo,false); int a=1,b=2; isFibo[1]=isFibo[2]=true; for(;;){ int t=a+b; a=b, b=t; if(t>100000) break; isFibo[t]=true; }}int main(){ //freopen("test.in","r",stdin); cin>>T; FiboD(); rep(t,1,T){ scanf("%d%d",&n,&m); rep(i,1,m) scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].c); sort(edge+1,edge+1+m,cmp); int mins=kruskal1(); int maxs=kruskal2(); printf("Case #%d: ",t); if(mins==-1 || maxs==-1) puts("No"); else{ bool flag=false; rep(i,mins,maxs) if(isFibo[i]){ flag=true; break; } if(flag) puts("Yes"); else puts("No"); } } //fclose(stdin);}
hdu 4786 Fibonacci Tree (最小、最大生成树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。