二分图匹配

二分图匹配

匹配 是指两两没有公共点的边集

给出一个二分图，找一个边数最大的匹配。

增广路：从一个未匹配点出发，依次经过未匹配边，匹配边...未匹配边到达一个未匹配点

增广：将增广路上的非匹配边和匹配边互换，得到的匹配比之前多一条边。

如果找不到增广路，那么已是最大匹配。

每次选一个未匹配点 进行 ，如果找不到 开头的增广路，换一个未匹配点进行 ，且以后再也不从 出发找增广路。如果存在一个从 出发的增广路，那么现在就找得到。

我们用 表示与 匹配的点

每一次匹配，我们用 来判断右节点有没有被访问过。

如果找到了增广路，依次更改 值即可完成增广。

注意尝试给左节点匹配的时候要清空 。

为什么这样可以保证得到的是增广路？

首先我们从 到 来尝试匹配，在尝试匹配之前， 是一定没有被访问过的，即 一定是未匹配点。

然后若 已匹配， 会被访问，此时 ， 通过 走的边一定是未匹配边。

带权二分图最佳完美匹配

算法，只适用于带权最大匹配一定是完美匹配的情况。

每个结点有一个可行顶标 ,任意边 满足: 。

开始 ， 然后 逐渐减小， 逐渐增大，

最终满足所选择的匹配边都满足

并且 最小。

例题：

Golden Tiger Claw

给定 矩阵，给每一行、每一列定一个值， 使得 和最小。

算法的副产物。跑一边 ， 即为所求。

Ants

平面上有 个黑点和 个白点，求一种方案，两两配对，边不相交。

最小匹配中不会出现线段相交。