一些 MST 的性质

forest114514 · 2024-12-18 15:18:31 · 个人记录

都要 5202 年了还不会最小生成树计数是不是时代的眼泪了。

1. 每个边权的边数量一定
2. 按顺序加入某些权值的边后缩成的图相同，显然只有某种边没加的时候缩点的图相同。

由此可以做点例题：

1. 最小生成树计数

   显然每种边的方案数独立，分别计算直接乘法原理即可，时间不会超过 O(n^3)。

2. CF891C Envy

   问某个边集能否同时出现在 MST 上，显然每种边权是独立的，然后可以扫描线+可撤销并查集做到 O(n+m+\sum k\log n)。