做题记录 25.9.5
szt100309
·
·
个人记录
\textcolor{black}\odot CF2041N Railway Construction
先将 n 个点按 a 从小到达重标号为 1\sim n，这一步时间复杂度 O(n\log n+m)，记 u 删除的出边到达的点的集合为 S_u，假定 S_u 已经从小到大排序
先考虑不删点情况下的求解
考虑类似 \text{Boruvka} 算法的过程，令每个点 u 找到不在 S_u 中的最小正整数 nb_u，并合并两者，显然一个计算一个 nb_u 的时间复杂度为 O(|S_u|) 的，这部分总时间复杂度 O(m)
此时只有 O(\sqrt {n+m}) 个连通块
证明：
- 显然 \sum nb_u\le n+m，因此至多有 O(\sqrt{n+m}) 个 nb_u 大于 \sqrt{n+m}
- 剩余 m-O(\sqrt{n+m}) 个点的 nb 都小于 \sqrt{n+m}，一步合并后至多得到 1\sim \sqrt{n+m} 所代表的 O(\sqrt{n+m}) 个连通块
- 剩余 O(\sqrt{n+m}) 个点每个点至多形成一个连通块，因此总数量为 O(\sqrt{n+m}) 的
从而最终 \text{MST} 中非叶子结点数量为 O(\sqrt{n+m}) 的
证明：
-
m-O(\sqrt{n+m})$ 个点的 $nb$ 小于 $\sqrt{n+m}$，将 $u>\sqrt{n+m}$ 且 $nb_u<\sqrt{n+m}$ 的 $(u,nb_u)$ 合并，得到 $\sqrt{n+m}$ 个菊花，此时非叶子结点数量为 $\sqrt{n+m}
- 剩余 O(\sqrt{n+m})+O(\sqrt{n+m})=O(\sqrt{n+m}) 个点依次合并到该图上，每次合并至多增加一个非叶子结点，因此总非叶子结点数量为 O(\sqrt{n+m})
假设已经求出初始 \text{MST}，然后依次考虑删去每个点
当删去的点为叶子时，显然直接从初始 \text{MST} 中删去对应点和边即为删点后图的 \text{MST}，这部分计算为 O(1) 的
若删去的点为非叶子，则按求 \text{MST} 的方式求出答案
因此原问题转化为 O(\sqrt{n+m}) 次 将原图划分为 O(\sqrt{n+m}) 个连通块，求出这些连通块的 \text{MST}，根据题目的范围，显然单次需要做到线性，以下只考虑其中一次
假如已经求出连通块两两之间的距离，则可用暴力 \text{Prim} 算法求出 \text{MST}，且时间复杂度为 O(\sqrt{n+m}^2)=O(n+m)，因此考虑如何求出两两之间的距离
用 B_i 表示一个连通块，令 id_u 为点 u 所在连通块的编号，假定 B_i 中数字从小到大排序，这一点容易在之前的处理中顺便保证
枚举一个连通块 B_i
对于每个 B_j\mid i\ne j 开一个边的桶，枚举 u\in B_i，枚举 v\in S_u，将 (u,v) 加入 B_{id_v} 的桶中，这一步总体时空复杂度为 O(\sum_i \sum_{u\in B_i}|S_i|)=O(\sum_u|S_i|)=O(n+m) 的
然后枚举连通块 B_j\mid i\ne j，考虑求解 dis(i,j)
枚举 B_j 的桶中的 (u,v)，每个点开一个桶，将 v 加入 u 对应的桶中（记得这一轮完毕后需要枚举 (u,v) 依次清空桶以保证复杂度）
显然这部分总体时间复杂度仍然为 O(n+m)，且由于初始的 S 已经排序，在以上操作过程中，每个点的桶内数字是递增的
然后依次枚举 u\in B_i，找到最小的不在 u 对应桶中但在 B_j 中的点 v，用 (u,v) 更新 dis(i,j)，若 u 对应桶已经空了，则跳出（显然当前 u 已经取到 v=\min B_j，之后的 u 一定不优）
显然按此方式时间复杂度为 O(n+m)，且正确性显然
这样一次求解的时间复杂度为 O(n+m)，总时间复杂度 O((n+m)\sqrt{n+m})
代码
参考