最小生成树专题-课余

未授课内容

7 个条目 · 点击条目切换内容

下载讲义 PDF
  1. 极差最小的生成树。

    • 二分极差 𝐷,滑窗得到每条边的活跃区间。
    • 时间分治 + 可撤销并查集判断某个窗口能否连通所有点。
    • 自环直接忽略。
    单独打开
  2. 构造恰好 𝑚 条边的连通简单图,边权为 𝑎𝑢𝑎𝑣。

    • 先按点权正负性构造完全图的 MST。
    • 再按点权排序,用多路归并补足剩余最小边。
    单独打开
  3. 把前面几个例题抽象成隐式图模型。

    • 边不显式给出,每轮只需为每个连通块回答最小出边查询。
    • oracle 查询要排除同块;常用“来自不同分量的前两名”。
    • Manhattan MST、XOR-MST、CF1305G 都是它的具体实例。
    单独打开
  4. 主理想类实例:把 oracle 化成 𝐼(𝑥)={𝑦:𝑦≤𝑥} 上的最值查询。

    • 布尔格:子集 Zeta 变换 / SOS DP,对应 CF1305G。
    • 树形偏序:子树对应 DFS 序区间,用区间最值查询。
    • DAG 可达性:原图和反图各查一个主理想,再合并。
    单独打开
  5. 核心事实:EMST 的每条边都是 Delaunay 边。

    所以二维算法是:先构造 Delaunay,再在 𝑂(𝑛) 条边上跑 Kruskal。

    单独打开
  6. Delaunay 三角剖分是平面点集的基本结构。

    • 空圆定义。
    • 二维边数 𝑂(𝑛),这让它成为 EMST 的候选边图。
    单独打开
  7. 二维 Delaunay 的分治构造。

    • 按 𝑥 坐标分治,递归构造左右两侧。
    • 合并时只补上下公切线之间的跨边。
    • 总复杂度 𝑂(𝑛log𝑛),难点在合并和 incircle 判定。
    单独打开
当前内容

知识点内容

点击左侧条目查看内容。

源码位置