Borůvka + 隐式图模型实例:主理想
Borůvka 隐式图模型中以主理想为核心的 oracle 实例:布尔格 Zeta 变换 / SOS DP、树形偏序子树最值、DAG 可达性的双主理想。标签 图论 / 生成树 / Borůvka / 问题模型 / 主理想
本页承接 Borůvka + 隐式图模型,收集 能化成 主理想查询的 oracle 实例。布尔格和树形偏序中 是一个主理想;DAG 可达性中 是原图与反图各一个主理想。其余 oracle 实例见 Borůvka + 隐式图模型实例。
这些实例的 oracle 都归结为主理想上的最值查询:一个主理想读一个 Zeta 表项,两个主理想分别查询后合并;排除当前分量仍用来自不同分量的前两名摘要。
以下沿用主模型页的记号: 表示边存在, 表示点权。
实例一:布尔格(Zeta 变换 / SOS DP)
每个点 对应一个 位掩码 ,掩码按子集关系构成偏序。令
谓词定义为
由于 等价于 ,所以 就是主理想 中的点。
沿用可分离边权 ,固定 后只需最大化 。对布尔格做 Zeta 变换(SOS DP),预处理出每个掩码 的主理想 上按 排序的前两名候选,且两项来自不同分量。查询 时取 ,从中选第一个分量不是 的候选即可。
每轮重建 Zeta 表的代价是 ,查询 ;总复杂度 ,空间 。
题目:CF1305G: Kuroni and Antihype:布尔格主理想 + 可分离点权边权的具体实例。
实例二:树形偏序(子树最值)
设每个点 对应一棵有根树上的节点 ,偏序取“后代 祖先”。节点 的主理想为
谓词定义为 。此时 ,查询就是主理想上的最值。
把树按 DFS 序展开,子树对应一个连续区间。用线段树维护区间内按 排序的前两名(来自不同分量),查询 时对区间取前两名摘要即可。
也可以自底向上合并子树摘要,预处理 ,查询 ;若每轮重建线段树,则每轮 。若 是少量子树之并,就合并少量区间。
实例三:DAG 可达性(祖先与后代最值)
给定 DAG 。把可达关系看作 偏序(允许零长度路径),谓词定义为
也就是两个不同点在该偏序下是否可比。
固定 后,满足 的点是 的其余祖先或其余后代。设 为把 的边全部反向得到的反图,记
为 的可达偏序中由 生成的主理想。类似地, 是反图中的主理想,也就是 在 中的后代集合。两个主理想都包含 ,所以
沿用模型页的可分离边权 ,查询变成
只要求出这两个主理想中“排除当前分量后的最优候选”,再取较大者即可。