最小差值生成树

边权极差最小的生成树;排序后滑窗得到加删边区间,二分答案并用时间分治与可撤销并查集判定。

来源 Luogu P4234 · 标签 生成树 / 二分答案 / 分治 / 可撤销并查集 / 滑动窗口

题目描述

给定一张点标号为 1 到 𝑛、有 𝑚 条边的无向连通图,边有边权。求一棵生成树,使树中最大边权与最小边权之差最小。图可能有自环。

1≤𝑛≤5×104,1≤𝑚≤2×105,1≤𝑢,𝑣≤𝑛,1≤𝑤≤104。

题解

二分答案 𝐷,判断是否存在边权极差不超过 𝐷 的生成树。自环不参与连通,直接忽略。

把边按权值升序排序。固定右端点 𝑟,令 𝑙𝑟 是最小的下标,使得

𝑤𝑟−𝑤{𝑙𝑟}≤𝐷

那么所有包含 𝑤𝑟 且极差不超过 𝐷 的边都落在窗口 [𝑙𝑟,𝑟] 中。若某个窗口能连通所有点,就存在合法的生成树;反过来,任何合法生成树在取最大边作为 𝑤𝑟 时也一定包含在某个窗口中。

窗口随 𝑟 增大而单调右移,可以用双指针求出每个 𝑙𝑟。对第 𝑖 条边,它出现在窗口中的时间是一个连续区间

𝑖≤𝑟≤𝑅𝑖

其中 𝑅𝑖 是满足 𝑤𝑟−𝑤𝑖≤𝐷 的最大 𝑟。把每条边的这个时间区间插入时间线段树,然后 DFS 整棵线段树,用可撤销并查集维护当前窗口的连通性。到达叶子 𝑟 时,如果并查集只剩一个连通块,就说明窗口 [𝑙𝑟,𝑟] 构成生成树,答案 𝐷 可行。

可撤销并查集按大小合并,不能路径压缩;每次回溯时撤销本层加入的边即可。二分 𝐷 的单调性显然:若 𝐷 可行,更大的 𝐷 也可行。

复杂度

排序为 𝑂(𝑚log𝑚)。每次判定把 𝑚 个区间插入线段树并做一次 DFS,复杂度 𝑂(𝑚log𝑚𝛼(𝑛));设边权值域为 𝑊,二分 𝑂(log𝑊) 次,总复杂度 𝑂(𝑚log𝑚log𝑊𝛼(𝑛)),空间 𝑂(𝑛+𝑚log𝑚)。

源码位置