2024 Nov

Question 1. [ARCY 2021] E. Planning Railroad Discontinuation

给定 \(l\) 张 \(n\) 个点 \(m\) 条边的图 \(G_i(0\leq i < l)\)，其中图 \(G_i\) 中连接 \(u,v\) 两个点的边的边权为 \(w_{u,v} + b_i\)。

在所有图中钦定 \(r\) 个点 \(s_1,s_2,\cdots, s_r\)，作为特殊点，其中点 \(G_i\) 的点 \(s_i\) 的特殊边仅连接 \(G_{(i-1)\bmod l}\) 与 \(G_{(i+1)\bmod l}\) 的点 \(s_i\)，边权分别为 \(a_{(i-1)\bmod l}\) 与 \(a_i\)。

记 \(G\) 是所有 \(G_i\) 与所有特殊边的并，求 \(G\) 的最小生成树。

\(n\leq 10^4, m,l \leq 10^5, w_{u,v},a_i,b_i\leq 10^9\)

nb 题。

首先让我们考虑 Kruskal 算法的过程：选出边权最小的边然后连上这条边。在本题中，由于 \(G\) 的点与边的数量巨大，无法直接执行 Kruskal，考察 \(G\) 的特殊性质。

让我们先将求 \(G_i\) 内部的生成树时，有效的边进行分类：连上这条边时，两个连通块均包含特殊点的，至少有一个不包含特殊点的。前者的所有边的边权按照从小到大的顺序记录下来，记为 \(S\)。

将所有 \(G_i\) 内部的生成树全部建好，然后考虑所有特殊边带来的贡献：减掉内部的边、连上特殊边。

还是根据 Kruskal，我们接下来要连通 \(G_i\)，那么肯定是根据 \(a_i\) 的升序考察，连出 \(l-1\) 组特殊边即可。

假设当前 \(a_i\) 两端的连通块的最小生成树已经求出，当前需要合并这两个连通块，那么肯定是 \(b_i\) 较大的那一边断开部分边，满足 \(w_{u,v} + b_j \ge a_i\)，这一点可以通过对 \(S\) 进行后缀和与二分求出数量与总和。

合并之后，两个连通块的 \(b_j\) 值肯定会取较小的那一个，不断重复直至所有连通块全部合并成功。

时间复杂度为 \(\mathcal{O}(m\log_2 m + l\log_2 r)\)。