P3101 [USACO14JAN] Ski Course Rating G 题解

KidA · 2023-12-02 15:40:47 · 题解

看到这题很容易想到对于每个起点进行二分 + bfs check，但这样写显然 T 飞。

然后由此我们想到用并查集维护连通块做，

具体地，我们先建出图，令每个格子向其右、下格子连边，边权为高度绝对差，

然后将边权从小到大排序，

考虑每一条边，若其端点未被合并，则将它们合并为同一集合，

顺便维护连通块的大小 sz_x 与起点个数 v_x，

若合并后集合大小 \ge T，则两边的集合中大小 \le T 的，其对于答案的贡献即为 此集合的起点个数 \times 当前边的边权。直接累加贡献即可。

时间复杂度 O(MN \log MN)。

代码。非常好写。