technique:general_matching_weighted
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
technique:general_matching_weighted [2021/07/04 22:58] toxel [优化] fix a bug |
technique:general_matching_weighted [2021/07/04 23:03] (当前版本) toxel [优化] clarify |
||
|---|---|---|---|
| 行 102: | 行 102: | ||
| 利用 KM 算法中的 $\text{slack}$ 变量，可以将复杂度优化到 $\mathcal{O}(n^{3})$。上述算法复杂度瓶颈在于 $S-\text{free}$ 边和 $S-S$ 边的计算。对于 $S-\text{free}$ 边，维护方法与 KM 中完全相同。 | 利用 KM 算法中的 $\text{slack}$ 变量，可以将复杂度优化到 $\mathcal{O}(n^{3})$。上述算法复杂度瓶颈在于 $S-\text{free}$ 边和 $S-S$ 边的计算。对于 $S-\text{free}$ 边，维护方法与 KM 中完全相同。 | ||
| - | 但是 $S-S$ 边额外要求它们不在同一朵花中。考虑维护任意两朵 $S$ 花之间的最小边权，及达到最小边权的边。由于增广时不会展开 $S$ 花，可以发现 $S$ 点只能产生不会消失。其中一部分复杂度是产生新的 $S$ 花时维护与其它 $S$ 花的最小边权，这可以暴力枚举边来实现，复杂度为 $\mathcal{O}(m)$。另一部分复杂度是缩花时需要重新计算该花到其它 $S$ 花的最小边权（其它 $S$ 花到它的最小边权显然不变）。注意到组成它的子花中，$S$ 花占了约一半，而一次增广中所有花的子花数量显然是 $\mathcal{O}(n)$ 的。因此，我们可以直接暴力枚举所有 $n$ 个点来进行更新，复杂度是 $\mathcal{O}(n^{2})$ 的。在这个基础上，就可以维护 $\text{slack}$ 变量了。 | + | 但是 $S-S$ 边额外要求它们不在同一朵花中。考虑维护任意两朵 $S$ 花之间的最小边权，及达到最小边权的边。由于增广时不会展开 $S$ 花，可以发现 $S$ 点只能产生不会消失。其中一部分复杂度是产生新的 $S$ 花时维护与其它 $S$ 花的最小边权，这可以暴力枚举边来实现，复杂度为 $\mathcal{O}(m)$。另一部分复杂度是缩花时需要重新计算该花到其它 $S$ 花的最小边权（其它 $S$ 花到它的最小边权显然不变）。注意到组成它的子花中，$S$ 花占了约一半，而一次增广中所有花的子花数量显然是 $\mathcal{O}(n)$ 的。因此，我们可以直接暴力枚举所有 $n$ 个点来进行更新，一次增广的复杂度是 $\mathcal{O}(n^{2})$ 的。在这个基础上，就可以维护 $\text{slack}$ 变量了。 |
| 总复杂度 $\mathcal{O}(n^{3})$。 | 总复杂度 $\mathcal{O}(n^{3})$。 | ||
technique/general_matching_weighted.1625410691.txt.gz · 最后更改: 2021/07/04 22:58 由 toxel
