最小生成树专题-课时2 最小生成树专题课时2:Borůvka 算法,以及 Rectilinear MST、XOR-MST、CF1305G 三个应用。 4 个条目 · 点击条目切换内容 下载讲义 PDF 01 知识Borůvka 算法 每一轮让每个连通块选出一条最小出边并同时合并,O(log n) 轮得到最小生成树。 每轮让每个连通块选最小出边,轮数为 𝑂(log𝑛)。这是后面隐式完全图模型的入口。 单独打开 02 题目Rectilinear MST 平面完全图边权为曼哈顿距离;算法一用 8 个八分圆候选边 + Kruskal,算法二用四象限 Borůvka。 完全图不能显式建边。先讲 8 个八分圆的候选边。再引出四象限 Borůvka。 单独打开 03 题目XOR-MST 完全图边权为异或值;用 Borůvka + 可删除二进制 trie,每轮查询块外最小异或边,O(B n log n)。 边权为 𝑎𝑖xor𝑎𝑗 的完全图。用 Borůvka 求 MST。每轮把当前块从二进制 trie 中删除,查询块外最小异或值,再插回。复杂度 𝑂(𝐵𝑛log𝑛),其中 𝐵 是值域位数。 单独打开 04 题目CF1305G: Kuroni and Antihype 把操作转化为最大生成树,用 Borůvka + max-plus Zeta 变换(SOS DP)求最大边。 把操作转化为最大生成树。边权为 𝑎𝑖+𝑎𝑗,边存在当 𝑎𝑖and𝑎𝑗=0。每轮用 max-plus Zeta 变换(SOS DP)为每个点找块外最大权候选。这与 XOR-MST 形成对照:一个用 trie,一个用子集最值。 单独打开 当前内容 知识点内容 上一节 下一节 单独打开 点击左侧条目查看内容。