记录一道前天5小时自闭赛没写出的题,之前讲座做过,QWQ
题目链接
题意:
n个点,m条边(起点、终点、权重)。任选一定量的边,构成生成树,并且符合题目给出的Fibonacci数中的其中一个,则输出”Yes”,否则输出”No”。
解法:
求一遍最小生成树,最大生成树,判断下是否存在至少一个Fibonacci数在这个两个值的中间。
假设符合,就可以把最小生成树(或者最大生成树)中的一些边换掉,使得总权重刚好等于一个Fibonacci数。(具体怎么换,那就脑补下?emmm)
生成树: n个点用n - 1条边连成的图
最小生成树:生成树中所有边权加起来最小的生成树
最大生出树:和最小生成树相反
ps:并查集做法记得初始化,否则像我一样调试好久
pps:题目给出的数据可能不会构成生成树,补题的时候WA了QwQ
代码:
1 |
|