最小差值生成树
边权极差最小的生成树;排序后滑窗得到加删边区间,二分答案并用时间分治与可撤销并查集判定。来源 Luogu P4234 · 标签 生成树 / 二分答案 / 分治 / 可撤销并查集 / 滑动窗口
题目描述
给定一张点标号为 到 、有 条边的无向连通图,边有边权。求一棵生成树,使树中最大边权与最小边权之差最小。图可能有自环。
,,,。
题解
二分答案 ,判断是否存在边权极差不超过 的生成树。自环不参与连通,直接忽略。
把边按权值升序排序。固定右端点 ,令 是最小的下标,使得
那么所有包含 且极差不超过 的边都落在窗口 中。若某个窗口能连通所有点,就存在合法的生成树;反过来,任何合法生成树在取最大边作为 时也一定包含在某个窗口中。
窗口随 增大而单调右移,可以用双指针求出每个 。对第 条边,它出现在窗口中的时间是一个连续区间
其中 是满足 的最大 。把每条边的这个时间区间插入时间线段树,然后 DFS 整棵线段树,用可撤销并查集维护当前窗口的连通性。到达叶子 时,如果并查集只剩一个连通块,就说明窗口 构成生成树,答案 可行。
可撤销并查集按大小合并,不能路径压缩;每次回溯时撤销本层加入的边即可。二分 的单调性显然:若 可行,更大的 也可行。
复杂度
排序为 。每次判定把 个区间插入线段树并做一次 DFS,复杂度 ;设边权值域为 ,二分 次,总复杂度 ,空间 。