二分匹配

匈牙利算法

参考链接

主要就是 能划分为 二分图，集合0中的元素之间不会有匹配关系，它只会和集合1中的元素有匹配关系，可能一对一一对多。同理集合2中的元素也是

常用的套路是 按照 奇偶 位置划分二分集合。

算法思路

首先 依次从左边集合中选出一个元素 和 右边集合中的元素匹配。如果右边集合中某个元素已经被占用了，那么根据它指向的左边集合中的元素号，递归的去调整它，以给当前元素腾位置。如果能腾出来，那么成功。否则返回false 算法实现的关键在于 一个记录 右边 到左边 的数组序号的映射关系，和 右边序号的访问情况。

算法时间复杂度，O(ExV) V为左边集合顶点的数目，E为图中的边数。每次去左边的一个顶点去和右边集合的顶点匹配，最坏情况就是把图中所有的边都遍历一遍才能找到可以匹配的结果。

例题

代码

int M, N;            //M, N分别表示左、右侧集合的元素数量
int Map[MAXM][MAXN]; //邻接矩阵存图
int p[MAXN];         //记录当前右侧元素所对应的左侧元素
bool vis[MAXN];      //记录右侧元素是否已被访问过
bool match(int i)
{
    for (int j = 1; j <= N; ++j)
        if (Map[i][j] && !vis[j]) //有边且未访问
        {
            vis[j] = true;                 //记录状态为访问过
            if (p[j] == 0 || match(p[j])) //如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
            {
                p[j] = i;    //当前左侧元素成为当前右侧元素的新匹配
                return true; //返回匹配成功
            }
        }
    return false; //循环结束，仍未找到匹配，返回匹配失败
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= M; ++i)
    {
        memset(vis, 0, sizeof(vis)); //重置vis数组
        if (match(i))
            cnt++;
    }
    return cnt;
}

KM算法

KM 算法是解决带权值的 二分匹配问题

参考链接

算法实现原理

基本原理也是依靠匈牙利算法，但是每个边都带了权重，因此思想是 取当前的最大子图 然后按照匈牙利算法去寻找完美匹配，如果无法实现完备匹配 就需要扩充最大子图。

通俗的算法原理：集合A中的1个元素都可以和B中的多个元素匹配，但是由于只能择其一，所以就选和B中匹配得分最大的边 联通，同理所有A中的点都这样筛选边，这样如果 A中的所有元素都和B中的有匹配（即实现完备匹配），那么此时图的匹配权重一定是最大。此时这就可以转化为匈牙利算法去搜索有无完备匹配。

如果没有实现完备匹配，那一定是有 n 个点 n-1 个边之间出现冲突。所以直观的应该放宽选取可匹配边的权重标准 让新的权重较小的边也加入图中，再尝试是否可以完备匹配，如果此时可以完备匹配 那么起始最终匹配的权重和相对初始的最大子图的完备匹配后的权重和（但是无法实现） 是 略微缩小的。KM算法就是通过一定的策略完成 扩充子图 -> 完备匹配 这个循环的，并保证 子图的权重 一定是 从初始最大 -> 小递减的 中间没有跳跃，所以最后匹配的权重和最大

• 寻找相等子图的完备匹配

实现步骤

1. 初始化可行顶标的值 (设定lx,ly的初始值)
2. 用匈牙利算法寻找相等子图的完备匹配
3. 若未找到增广路则修改可行顶标的值
4. 重复(2)(3)直到找到相等子图的完备匹配为止

实现子图扩充最优 要 按照两个原则来实现：

• 可行顶标
• 可行边，顶点的定标和 等于 边的权重 为一个可行边 可以加入相等子图中