题解：P17484 月兔通信网络

· · 题解

Sol

有一个结论：如果加 n-1 条边之后凑不出完全图，那么就不可能做到最大值小于 2。小证下，就是没直接连边的那对得经过至少一次中转，所以最大值至少得是 2。

所以如果能凑出来完全图就凑出来，否则，简单的一个构造就是构造菊花，此时最大值显然 2，况且构造边数上限正好是 n-1 条（遇到原图有的边就跳过），易证这是前置条件下最优秀的构造。