MST

一句话理解

MST 最小生成树：边权和最小的生成树。

为什么要学

修路总费用最小。

讲解

Kruskal 或 Prim。边权可正可负，但不能指望唯一。

例子

总长度最短的光缆网。

常见错误

• 有向图当 MST。
• 不连通求 MST 应求森林。