最小生成树专题-课余
未授课内容
-
单独打开
极差最小的生成树。
- 二分极差 ,滑窗得到每条边的活跃区间。
- 时间分治 + 可撤销并查集判断某个窗口能否连通所有点。
- 自环直接忽略。
-
单独打开
构造恰好 条边的连通简单图,边权为 。
- 先按点权正负性构造完全图的 MST。
- 再按点权排序,用多路归并补足剩余最小边。
-
单独打开
把前面几个例题抽象成隐式图模型。
- 边不显式给出,每轮只需为每个连通块回答最小出边查询。
- oracle 查询要排除同块;常用“来自不同分量的前两名”。
- Manhattan MST、XOR-MST、CF1305G 都是它的具体实例。
-
单独打开
主理想类实例:把 oracle 化成 上的最值查询。
- 布尔格:子集 Zeta 变换 / SOS DP,对应 CF1305G。
- 树形偏序:子树对应 DFS 序区间,用区间最值查询。
- DAG 可达性:原图和反图各查一个主理想,再合并。
-
单独打开
核心事实:EMST 的每条边都是 Delaunay 边。
所以二维算法是:先构造 Delaunay,再在 条边上跑 Kruskal。
-
单独打开
Delaunay 三角剖分是平面点集的基本结构。
- 空圆定义。
- 二维边数 ,这让它成为 EMST 的候选边图。
-
单独打开
二维 Delaunay 的分治构造。
- 按 坐标分治,递归构造左右两侧。
- 合并时只补上下公切线之间的跨边。
- 总复杂度 ,难点在合并和 incircle 判定。
当前内容
知识点内容
点击左侧条目查看内容。