标签:生成树
18 个条目
-
概念 最小生成树
带权连通图中边权和最小的生成树;由割性质与环性质刻画,不一定唯一。
2026-11-15 -
概念 双权瓶颈路径
每条边有两个权值 (a,b),最小化路径上 max a + max b;按 a 扫描,用按 b 的 MST 回答瓶颈。
2026-11-12 -
题目 Earthquake
每条边有成本 c 和时间 t,最大化 (f - Σc) / Σt;二分答案后把边权改为 c + p t,用最小生成树判定。
2026-11-12 -
平面完全图边权为曼哈顿距离;算法一用 8 个八分圆候选边 + Kruskal,算法二用四象限 Borůvka。
2026-11-12 -
概念 生成树
连通无向图中包含全部顶点的一棵树;恰有 n-1 条边,是 MST、生成森林和树形结构的基础。
2026-11-11 -
概念 瓶颈生成树
以最小化最大边权为目标的生成树;任一棵 MST 都是瓶颈生成树,但反过来不一定。
2026-11-10 -
概念 最小生成森林
不连通带权无向图中,每个连通块各取一棵 MST 得到的最小权森林;连通时退化为 MST。
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 -
题目 01-MST
完全图边权只有 0/1,给定权值为 1 的边;MST 权值为 0 边补图的连通分量数减 1。
2026-11-10 -
把操作转化为最大生成树,用 Borůvka + max-plus Zeta 变换(SOS DP)求最大边。
2026-11-10 -
题目 Envy
多次询问一组边能否同时属于某棵 MST;按权值分组,用 Kruskal 的连通块不变性和可撤销并查集判定。
2026-11-10 -
平面点集的完全图边权为欧氏距离;用 Delaunay 三角剖分 + Kruskal 在 O(n log n) 时间求 MST。
2026-11-10 -
构造 m 条边的连通简单图,边权为 a_u a_v;先求 MST,再用排序后的点权多路归并选剩余最小边。
2026-11-10 -
双权瓶颈路径:最小化路径上 max a + max b;按 a 排序,用 LCT 动态维护按 b 的 MST。
2026-11-10 -
题目 最小差值生成树
边权极差最小的生成树;排序后滑窗得到加删边区间,二分答案并用时间分治与可撤销并查集判定。
2026-11-10 -
题目 XOR-MST
完全图边权为异或值;用 Borůvka + 可删除二进制 trie,每轮查询块外最小异或边,O(B n log n)。
2026-11-10