最小生成树专题-课时2

最小生成树专题课时2:Borůvka 算法,以及 Rectilinear MST、XOR-MST、CF1305G 三个应用。

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

下载讲义 PDF
  1. 每轮让每个连通块选最小出边,轮数为 𝑂(log𝑛)。

    这是后面隐式完全图模型的入口。

    单独打开
  2. 完全图不能显式建边。

    • 先讲 8 个八分圆的候选边。
    • 再引出四象限 Borůvka。
    单独打开
  3. 边权为 𝑎𝑖xor𝑎𝑗 的完全图。

    • 用 Borůvka 求 MST。
    • 每轮把当前块从二进制 trie 中删除,查询块外最小异或值,再插回。
    • 复杂度 𝑂(𝐵𝑛log𝑛),其中 𝐵 是值域位数。
    单独打开
  4. 把操作转化为最大生成树。

    • 边权为 𝑎𝑖+𝑎𝑗,边存在当 𝑎𝑖and𝑎𝑗=0。
    • 每轮用 max-plus Zeta 变换(SOS DP)为每个点找块外最大权候选。
    • 这与 XOR-MST 形成对照:一个用 trie,一个用子集最值。
    单独打开
当前内容

知识点内容

点击左侧条目查看内容。

源码位置