【匹配】匈牙利匹配算法

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
}