【匹配】匈牙利匹配算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了【匹配】匈牙利匹配算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

every blog every motto: You can do more than you think.
https://blog.csdn.net/weixin_39190382?type=blog

0. 前言

匈牙利匹配算法

1. 正文

1.1 基础概念

二分图

顶点分为两个集合，集合间顶点相连，集合内点不相连

【匹配】匈牙利匹配算法,# 算法合集,算法

匹配

一个匹配就是一个边的集合，其中，任意两条边不存在公共的顶点

最大匹配

上图中，我们能找到多组匹配，在这其中，所含匹配变数最多的的匹配，成为最大匹配。

交替路

从一个未匹配的点出发，依次经过非匹配边，匹配边，非匹配边，这样形成的路称为交替路

增广路

从一个未匹配的点出发，走交替路，如果途径另一个未匹配点（起点不算），则这条交替路称为增广路

1.2 算法流程

1.2.1 通俗理解

概括： 先到先得，能让则让

对于如下已有的匹配，我们需要寻找他的最大匹配。
【匹配】匈牙利匹配算法,# 算法合集,算法

1.2.2 步骤

下面以经典的配对情景进行说明。

现在有boys和girls两个点集，每个人有各自的暧昧对象（可能有多个），现在要把他们配情侣，最多能配多少对？（即，寻找最大匹配数）

说明：

边表示暧昧关系

注意：

不能搞基哦
不能脚踏多只船

【匹配】匈牙利匹配算法,# 算法合集,算法
先从B1看起，他与G2有暧昧，那么先暂时他们配成一对。
注意： 这里突出了先到先得

【匹配】匈牙利匹配算法,# 算法合集,算法
再看B2，B2也可G2纠缠不清，那么我们看G2现在有男友吗？有的，是B1。那B1有没有其他暧昧对象呢？花心男果然是花心男，还有一个G4，同时，G4还没有安排对象。那么把B1和G4配成一对。

注意： 这里突出了能让则让
【匹配】匈牙利匹配算法,# 算法合集,算法
再接着，我们看B3，他这G1直接配对就好。

最后我们看B4，他的暧昧对象是G4，但是G4现在已经有男友了。按照之前的思路，往前到，看看能不能让一让的。发现没法让，所以B4只能单着了。
同时，G3也只能单着。

注意： 这里依然是能让则让，让不了也没法

【匹配】匈牙利匹配算法,# 算法合集,算法
至此，找到一个了最大匹配，但是最大匹配不是固定的。如果从girls这边开始或者从B4开始情况可能就不一样了。但是最大匹配数是一样的。

1.2.3 代码实现

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<=N; ++i){
        memset(vis,false,sizeof(vis)); // 重置vis数组
        if(match(i)) cnt++;
    }
    return cnt
}