CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

这个算法大家都写了很多，这里只想证明 KM 算法有局部最优性。即第 $i$ 轮求出的匹配是 $\text{size}=i$ 的最大权匹配。

对通常流传的 KM 算法需要做一定修改，即将所有 $U$ 部全体未盖点均作为 $S$ 点。设一轮结束后，$U$ 中的匹配点是 $U_{1}$，未盖点是 $U_{2}$，$V$ 中匹配点是 $V_{1}$，未盖点是 $V_{2}$。由于未盖点历史上必然一直是未盖点，因此 $U_{2}\subset S$ 一直成立，所以其中点的对偶变量必然一直是最小的，因为每次松驰都会减它的权值。同理，$V_{2}\subset T'$ 也一直成立，因为只有匹配点才有资格进入 $T$。因此每次松驰的时候它们都没资格增加权值，从而永远是 $0$。反过来说，$U_{1}$ 和 $V_{1}$ 中的点则是权值最大的一批点。因此对于任意 $\text{size}=i$ 的匹配有

$$
\le\sum_{j\in U_{1}}y_{j}+\sum_{j\in V_{1}}y_{j}=\text{current answer}
$$

CVBB ACM Team

用户工具

站点工具

页面工具