最小生成树专题-课时1
最小生成树专题课时1:MST 性质、Kruskal、Prim,以及 01-MST、Earthquake、Envy 三个基础例题。
-
单独打开
开场先区分 MST 与最短路:MST 最小化的是所有选中边的权值和,不是两点间路径长度。
- 用 割性质 解释为什么最小横跨边是安全的。
- 用 环性质 解释为什么最大环边可以删掉。
-
单独打开
先排序,再从小到大尝试加边。
- 并查集负责判断是否成环。
- 选满 条边就可以提前退出。
-
单独打开
从点集扩展,适合稠密图。
对比 Kruskal:一个按边排序,一个维护到当前树的最小距离。
-
单独打开
完全图边权只有 和 ,显式给出的是 边。
- 先尽量选 边,把 边连通块缩成点。
- 答案等于 边图补图的连通块数减一。
- 补图边太多,用 BFS 和有序集合维护未访问点。
可以从 Prim 算法框架开始推导。类似 Prim 的当前弧优化版本。
-
单独打开
最优比率生成树:二分 ,把边权改成 。
- 判定最小生成树权和是否不超过 。
- 无利可图时输出
0.0000。
-
单独打开
询问一组边能否同时出现在某棵 MST 中。
- 同权边的数量固定。
- 小于 的边形成的连通块也固定。
- 按权值离线处理,同权询问边用可撤销并查集判环。
当前内容
知识点内容
点击左侧条目查看内容。