滑雪场评级 题解

思路

把每个格子视为顶点，相邻格子之间连一条边，边权为两格海拔差的绝对值。给定阈值 $D$ 时，起点能够到达的格子正是只保留边权不超过 $D$ 的边后，它所在连通分量的全部顶点。

因此，一个起点的评级就是：按边权从小到大加入边时，该起点所在连通分量的大小第一次达到 $T$ 的边权。

子任务 1 的图是一条链。起点能够到达的区域一定是包含它的连续区间。只需枚举所有包含该点、长度恰为 $T$ 的区间，取区间内部最大相邻高度差的最小值。用区间最大值稀疏表后，每个区间可 $O(1)$ 查询。

子任务 2 可以枚举所有可能阈值。对每个起点和每个阈值做广度优先搜索，找到第一个可达格子数不少于 $T$ 的阈值。

子任务 3 的起点不超过 $20$ 个。对每个起点单独运行 minimax Dijkstra：到一个格子的距离定义为路径上最大边权的最小值。第 $T$ 个确定最小距离的格子对应的距离就是评级。

满分做法统一进行一次 Kruskal 扫描。

做法

建立所有上下左右相邻边，并按高度差从小到大排序。并查集的每个根维护：

• 当前连通分量的格子数；
• 该分量中还没有确定评级的起点数量。

依次处理边。若边的两端已在同一分量中则跳过；否则合并两个分量。

若合并后分量大小达到 $T$，那么其中所有尚未确定评级的起点，其评级都等于当前边权。把当前边权乘以尚未结算的起点数加入答案，并把该数量清零。

已经清零的成熟分量以后可能与新分量合并。新分量中尚未结算的起点仍会随并查集合并进来，并在当前边权处结算，因此同一个起点恰好结算一次。

当 $T=1$ 时，每个起点在阈值 $0$ 时已经能到达自身，答案为 $0$。

正确性证明

按非降顺序处理到边权 $w$ 后，并查集中的连通分量恰好等于只保留权值不超过 $w$ 的边后图的连通分量。这是 Kruskal 扫描的直接不变量。

考虑一个尚未结算的起点 $P$。在处理当前边之前，它所在分量大小小于 $T$，否则它早已在第一次达到 $T$ 时结算。当前合并后若分量大小达到 $T$，根据不变量，阈值 $w$ 已使 $P$ 至少可达 $T$ 个格子；而任何更小阈值都不可以。因此 $P$ 的最小评级恰为 $w$。

一次合并可能使多个起点同时首次满足条件，程序按尚未结算起点数统一累加。随后将数量清零，保证这些起点以后不再重复计入；未来并入的未结算起点仍保留在另一分量的计数中，并会在合并后的当前阈值正确结算。

所以每个起点都恰好在其连通分量第一次达到 $T$ 时，以正确的最小阈值计入答案，最终总和正确。

复杂度分析

网格有 $MN$ 个顶点和 $O(MN)$ 条边。排序复杂度为 $O(MN\log(MN))$，并查集操作总复杂度为 $O(MN\alpha(MN))$。

总时间复杂度为 $O(MN\log(MN))$，空间复杂度为 $O(MN)$。