某场比赛 最大化

题目描述

有一张 $n$ 个点的无向图，要求给每一个点分配一个标号，使得任意一条边两端的点的标号差的绝对值不能超过给出的常数 $D$，要求在此基础上最大化标号的最大值与最小值的差

$n\le 1000$

Solution

答案为两两间最短路的最大值

证明：

注意到以某个点为起点进行 $bfs$ 的时候，我们可以按照深度 $k$ 分配标号为 $kD$

原因很简单，因为无向图的 $bfs$ 树只会出现到兄弟的边，而兄弟之间的标号是相等的

然后我们发现 $bfs$ 求出的每个点的深度就是最短路