Codeforces 1026D – Shortest Cycle

题目链接:Codeforces 1026D

根据鸽巢原理,当抽屉数量为$64$的时候,如果大于$64 \times 2 + 1 = 129$个物品,可以保证有一个抽屉中出现三个物品。

也就是说,在这一题中,我们只需要去掉所有为零的元素,在剩下的$r$个元素中随意取$\min \{ r, 129  \}$个出来寻找最小环即可。

这里可以使用Floyd算法求最小环,时间复杂度$O(129 ^ 3)$。

 

说点什么

avatar
50
  Subscribe  
提醒