匈牙利算法

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。 美国数学家哈罗德·库恩于1955年提出该算法。 此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。

前言

在学校一堆破事之中找到了时间来学算法。
刚开始查资料的时候找到很多，都是用很专业的话在介绍匈牙利算法，但这种方式确实不适合学习。
最后找到这篇博客，用比较容易理解的方式讲了匈牙利算法的过程：

趣写算法系列之—匈牙利算法

继续往下看之前先把上面的博客看了，很有帮助的。

二分图

图一：一个二分图的实例

如果图 $G=(U,V,E)$中，$U$和$V$为不相交的点集，且 $E = \{(u,v)|u \in U ,v \in V\}$，则 $G$ 为二分图。通俗点讲就是图内的点可以分成两个集合，且每条边都是跨接在这两个集合间的，那这个图就是二分图。
最常见的例子就是把男生和女生分开，且每个人都对多个异性有好感（震惊.jpg（不考虑特殊性取向（当然也可以换别的例子但我想不到）））。

匈牙利算法

匈牙利算法（Hungarian Algorithm）听起来很难学（确实人名（地名）算法听起来比较强），但基本思路比较简单，是用来解决二分图最大匹配问题的。

图的匹配

图二：二分图的匹配

匹配是指从图中找到边可以使左点集和右点集一一匹配，设匹配边数量为 $M$，当 $M$ 达到最大时即为最大匹配。

算法过程

匈牙利算法有 dfs 和 bfs 版本，这里介绍比较简单的 dfs 版本，bfs 还没学（逃。
要用到递归的话，首先要明确单个 dfs 树的目的，这里是找到当前点的匹配。
下面开始分步详解。

图三：点 1 的匹配

图(a)，点 1 的第一条边指向了点 5，点 5 此时没有被匹配，所以点 1 可以和点 5 匹配。

图四：点 2 的匹配

图(b)，开始匹配点 2，点 2 的第一条边指向点 5，但点 5 已经被点 1 匹配，所以开始和与点 5 配对的点 1 协调，尝试使点 1 匹配其它点。

图五：点 2 的匹配,协调点 1

图(c)，点 1 的协调过程，点 1 开始尝试它的第二条边，指向点 7，点 7 此时没有被匹配，所以点 1 可以和点 7 匹配。

图六：点 3 的匹配

图(d)，点 2 对点 1 的协调完成，于是点 2 匹配点 5,点 1 匹配点 7。
点 3 开始尝试匹配，第一条边指向了点 5 ，开始和与点 5 配对的点 2 协调

图七：点 3 的匹配,对点 2 协调失败，换一条边

图(e)，由于点 2 没有其它边了，只能匹配点 5,所以点 3 对点 2 的协调失败，尝试下一条边，指向点 6,点 6 此时没有被匹配，所以点 3 可以和点 6 匹配。

图八：点 4 的匹配

图(f)，点 4 的第一条边指向点 7，点 7 已经被点 1 匹配，和刚才一样的情况，点 1 显然已经没法继续协调，所以点 4 要尝试下一条边

图九：点 4 的匹配

图(g)，点 4 尝试第二条边，和点 8 匹配。

整个流程就是这样，是点和点相互协调的过程，协调这步就可以用递归来完成。

伪代码

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#define MAXN 505

vector<int> G[MAXN];
int timestamp[MAXN];
int mch[MAXN];


/**
 *@function:    bool hungarian(int u,int time)
 *@param:       u: 节点 u,在图的左部
 *              time: 时间戳
 *@return:      true: 匹配成功
 *              false: 匹配失败
 *@note:        使用时需要已经明确图的左部和右部
 */
bool hungarian(int u,int time)
{
    // 在本轮 dfs 树已经被访问过
    if(timestamp[u] == time) return false;
    // 标上时间戳
    timestamp[u] = time;

    for(int v: G[u])
    {
        //      未匹配               协调成功
        if((mch[v] == 0) || hungarian(mch[v],time))
        {
            mch[v] = u;
            return true;
        }
    }

    return false;
}

使用

1
2
3
4
5
6
7
//记录匹配边的数量
int ans = 0;
// 只遍历左部点
for(int i = 1;i <= n;i++)
{
    if(hungarian(i,i)) ans++;
}

应用

二分图的最大匹配

【模板】二分图最大匹配-Luogu-P3386
COURSES-POJ-1469

二分图最小点覆盖

最小点覆盖是指：在图 $G(U,V,E)$ 中，一个最小的点集 $S=\{P| P \in U or P \in V\}$，使得图内的每条边都至少有一个端点在点集 $S$ 内。
可以证明在二分图中 二分图最小点覆盖 = 最大匹配。怎么证明这里就不写了

Asteroids-POJ-3041

最小路径覆盖

最小路径覆盖指：用尽量少的不互相交叉的简单路径覆盖图 $G$ 的所有顶点
可以证明二分图中 最小路径覆盖 = 顶点数 - 最大匹配

Air Raid-POJ-1422

后记

感谢学校团委，没有他们举办的活动的衬托我不可能知道学习算法是多么轻松快乐。
感谢楼下和桥下的四果汤店，在我饱受折磨的时候恢复心情。