标签:Borůvka
8 个条目
-
概念 Borůvka 算法
每一轮让每个连通块选出一条最小出边并同时合并,O(log n) 轮得到最小生成树。
2026-11-15 -
平面完全图边权为曼哈顿距离;算法一用 8 个八分圆候选边 + Kruskal,算法二用四象限 Borůvka。
2026-11-12 -
概念 Borůvka 算法实现
Borůvka 算法的并查集实现,含调用示例和实现细节。
2026-11-10 -
隐式稠密图上用 Borůvka 的 O(log n) 轮,把每轮化为最优出边 oracle;具体谓词结构与 SOS DP 见实例页。
2026-11-10 -
Borůvka 隐式图模型的实例索引:主理想、Rectilinear MST、XOR-MST,以及通用的紧凑最值查询条件。
2026-11-10 -
Borůvka 隐式图模型中以主理想为核心的 oracle 实例:布尔格 Zeta 变换 / SOS DP、树形偏序子树最值、DAG 可达性的双主理想。
2026-11-10 -
把操作转化为最大生成树,用 Borůvka + max-plus Zeta 变换(SOS DP)求最大边。
2026-11-10 -
题目 XOR-MST
完全图边权为异或值;用 Borůvka + 可删除二进制 trie,每轮查询块外最小异或边,O(B n log n)。
2026-11-10