最小生成树专题-课时1

最小生成树专题课时1:MST 性质、Kruskal、Prim,以及 01-MST、Earthquake、Envy 三个基础例题。

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

下载讲义 PDF
  1. 开场先区分 MST 与最短路:MST 最小化的是所有选中边的权值和,不是两点间路径长度。

    • 用 割性质 解释为什么最小横跨边是安全的。
    • 用 环性质 解释为什么最大环边可以删掉。
    单独打开
  2. 先排序,再从小到大尝试加边。

    • 并查集负责判断是否成环。
    • 选满 𝑛−1 条边就可以提前退出。
    单独打开
  3. 从点集扩展,适合稠密图。

    对比 Kruskal:一个按边排序,一个维护到当前树的最小距离。

    单独打开
  4. 完全图边权只有 0 和 1,显式给出的是 1 边。

    • 先尽量选 0 边,把 0 边连通块缩成点。
    • 答案等于 1 边图补图的连通块数减一。
    • 补图边太多,用 BFS 和有序集合维护未访问点。

    可以从 Prim 算法框架开始推导。类似 Prim 的当前弧优化版本。

    单独打开
  5. 最优比率生成树:二分 𝑝,把边权改成 𝑐+𝑝𝑡。

    • 判定最小生成树权和是否不超过 𝑓。
    • 无利可图时输出 0.0000。
    单独打开
  6. 询问一组边能否同时出现在某棵 MST 中。

    • 同权边的数量固定。
    • 小于 𝑡 的边形成的连通块也固定。
    • 按权值离线处理,同权询问边用可撤销并查集判环。
    单独打开
当前内容

知识点内容

点击左侧条目查看内容。

源码位置