P2504 [HAOI2006] 聪明的猴子 分析

· · 个人记录

本题虽然没有图，但是是明显的图论题。一只猴子想要到达所有的树，当且仅当它的跳跃能力要大于等于到所有树的最大距离。

这个“到所有树的最大距离”，很明显是最小生成树。

于是求出最小生成树，并且维护最大距离。之后对每一个猴子进行比较即可。

复杂度 O(N^2 + M)。