大致题意:
一个无向图中,每条边都是白边或者是黑边中的一种,问是否存在这个图的一颗生成树使得生成树中白边的个数为一个斐波那契数。
大致思路:
求出生成树中白边可能的最大值和最小值,如果某个斐波那契数包含在最大值和最小值之间,则可判定存在这样的生成树。
要注意判定这个图是否联通
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> using namespace std; const int nMax = 100020; struct data{ // 每条边的数据结构。 int u, v, w; }edge[nMax]; int n, m, pa[nMax]; bool cmp(data a, data b){ if(a.w < b.w) return true; return false; } bool cmp1(data a, data b){ if(a.w > b.w) return true; return false; } void make_set(){ // 并查集:建立。 for(int x = 1; x <= n; x ++) pa[x] = x; } int find_set(int x){ // 并查集:查找。 if(x != pa[x]) pa[x] = find_set(pa[x]); return pa[x]; } int kruskal(int f){ int i, ans = 0; make_set(); if(f)sort(edge, edge + m, cmp); // 对所有边按照权值从小到大排序。 else sort(edge, edge + m, cmp1); for(i = 0; i < m; i ++){ int x = find_set(edge[i].v); int y = find_set(edge[i].u); if(x != y){ pa[y] = x; ans += edge[i].w; } } return ans; } int fib[25]={1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,28657,46368,75025,121393}; int main(){ int i,k,t,ttt; scanf("%d",&ttt); for(t=1;t<=ttt;t++){ scanf("%d%d",&n,&m); for(i=0;i<m;i++){ scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); } int a=kruskal(1); int b=kruskal(0); if(a>=b){ k=a,a=b,b=k; } bool flag=1; for(i=2;i<=n;i++){ if(find_set(i)!=find_set(1)){ flag=0; break; } } if(!flag){ printf("Case #%d: No\n",t); continue; } flag=0; for(i=0;i<24;i++){ if(a<=fib[i]&&b>=fib[i]){ flag=1; break; } } if(flag)printf("Case #%d: Yes\n",t); else printf("Case #%d: No\n",t); } }
相关推荐
Kruskal算法,用C语言进行描述,有注释
代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal...
Kruskal算法python实现,包括无向图的绘制,需要自己在桌面上先建关于无向图的TXT
用matlab编写的kruskal算法,已编译
实现了kruskal的算法,测试可行。
输入mapping前后的数据,输出Kruskal Stress值,以及相应的图。Take points before and after mapping, then you'll get the Kruskal Stress factor and the figure.
c++编的kruskal法最小生成树的实现
编写算法能够建立带权图,并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
对给定的图结构,实现求解最小生成树的Kruskal算法。每次在满足和已选边不构成回路的条件下选择一条权植最小的边,添加到新的生成数中。Kruskal算法的实现类似于计算连通枝的算法。它使用了分离集合数据结构以保持数...
《算法导论》之图论章节中最小生成树的Kruskal算法。
克鲁斯卡尔算法(即 Kruskal)的一种 Python 代码实现,这是最经典的一种图算法之一,对于图G(V,E),借助这个算法可以得到其最小生成树。
邻接矩阵 Kruskal 算法的相关实现。代码完美可运行。
用Kruskal算法实现若干个城市之间的最短路径.最大城市数目为7个。
所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。这一步可以直接使用库函数qsort或者sort。接下来从小到大依次考察每一条边(u,v)。 具体实现过程如下: <1> 设一个有n个顶点的连通网络为G(V,E)...
最小生成树kruskal算法
prim算法 Kruskal算法分别实现最小生成树
算法分析与设计中的kruskal算法!
用KrusKal算法求最小生成树问题。对一个带权无向图,求其最小生成树,本程序功能通过KrusKal算法实现。
Kruskal算法的一种改进--二分Kruskal算法,黄荣明,,最小生成树是数据结构中图的一个重要部分,它有许多重要的实际应用。如何方便快捷地找到最小生成树,具有极其重要的现实经济意义
Kruskal算法:使用Kruskal算法求解下面两图的最小生成树。 使用矩阵表示两图,输出最小生成树的点、边和权。