二分图匹配
匹配 是指两两没有公共点的边集
给出一个二分图,找一个边数最大的匹配。
增广路:从一个未匹配点出发,依次经过未匹配边,匹配边...未匹配边到达一个未匹配点
增广:将增广路上的非匹配边和匹配边互换,得到的匹配比之前多一条边。
如果找不到增广路,那么已是最大匹配。
每次选一个未匹配点 进行 ,如果找不到 开头的增广路,换一个未匹配点进行 ,且以后再也不从 出发找增广路。如果存在一个从 出发的增广路,那么现在就找得到。
我们用 表示与 匹配的点
每一次匹配,我们用 来判断右节点有没有被访问过。
如果找到了增广路,依次更改 值即可完成增广。
注意尝试给左节点匹配的时候要清空 。
为什么这样可以保证得到的是增广路?
首先我们从 到 来尝试匹配,在尝试匹配之前, 是一定没有被访问过的,即 一定是未匹配点。
然后若 已匹配, 会被访问,此时 , 通过 走的边一定是未匹配边。
带权二分图最佳完美匹配
算法,只适用于带权最大匹配一定是完美匹配的情况。
每个结点有一个可行顶标 ,任意边 满足: 。
开始 , 然后 逐渐减小, 逐渐增大,
最终满足所选择的匹配边都满足
并且 最小。
例题:
给定 矩阵,给每一行、每一列定一个值, 使得 和最小。
算法的副产物。跑一边 , 即为所求。
平面上有 个黑点和 个白点,求一种方案,两两配对,边不相交。
最小匹配中不会出现线段相交。