算法详解——无权二分图最大匹配匈牙利算法

Warning

由于本博客作者实在是太弱啦，本篇文章可能存在大量的错误，漏洞，不规范，不合法之处。若您发现本文章所存在的任何问题，请您尽快在评论区指出，十分感谢！

另外，本文随意转载，但请注明出处。

问题

你遇到了这样的问题：

有 n 个驾驶员，驾驶员可以开坦克！
有 m 辆不同种类的坦克车！每个驾驶员只能开其中一些种类的坦克车，比如 59 式坦克，59-改，黄金 59...
显然的，每个驾驶员只能开一辆坦克，所以有些坦克可能没人开，相应的，有些驾驶员可能并不需要开坦克。
总书记希望可以开动最多数量的坦克，由于他还要去天安门见群众，所以安排驾驶员的工作就交给你啦！
尝试安排一种分配方案，使得尽可能多的驾驶员有坦克开！

n,m≤1000

约定

在下面可能会出现的相关图片中，位于左侧的节点各代表一个驾驶员，位于右侧的节点各代表一辆不同的坦克，黑色连线代表一种可以驾驶的关系，红色连线代表我们满足了这组关系

对于“”中的内容，感性理解...

骗分

遇到不会做的问题怎么办呢，首先尝试骗分是一个合格的 OIER 的基本素养（大雾 ...

我们考虑使用一种贪心策略，对于一个驾驶员，只要它还有可以开的坦克，就把坦克分配给他，直到不能分配为止，但是... 这么做的错误是显然的，对于下图 (1) 的情况，显然 1-6,2-7,3-8,4-5 的方案更优

(1)

考虑原因，为什么出现了这种错误了呢？当我们在分配 1-5 时，并没有考虑到 1-6 这个选择，诚然，在程序执行到这一步时并没有带来影响，但是当 4-5 试图匹配时，就不可行了，于是我们尝试修改这个策略

解决

策略的缺陷在于选择匹配后就固定了这种选择，我们尝试为策略加入一种“后悔”机制，当我们尝试为一个点 i 匹配点 j 时，若点 j 已经匹配了点 k，尝试去为点 k 分配一个新的匹配点，"释放"点 j，将点 i 与点 j 匹配~

这样做是肯定不会使得结果变得更劣的，因为任意对的匹配的权重相同~相反，若我们能完成这种“后悔”操作，使得点 i,j 匹配，则会比放弃这对匹配更优

这就是匈牙利算法~

实际实现是这样递归的：当我们试图匹配 i,j，就要尝试是否能为 k 分配另一个匹配点，若 k 的另一个匹配点也已经被匹配则继续递归... 出口在成功找到一组匹配为 i,j“腾出地方”或尝试所有可能仍然无法做到... 在实际实现中，对于一个点，我们尝试更换它的匹配只需要执行一次，使用 vis 数组记录是否尝试过改变它的匹配，lk 数组记录目前的匹配。于是理解代码应该是不困难的了...

代码

bool vis[410];//为了简短，代码中删去了不必要的数据读入，处理输出等部分
int lk[410];
bool find(int x)
{
    for(int i=head[x];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(!vis[to])
        {
            vis[to]=1;
            if(!lk[to]||find(lk[to]))
            {
                lk[to]=x;
                return 1;
            }
        }
    }
    return 0;
}
int n,m,ans;    
int main()
{
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(find(i))ans++;
    }
}

bool vis[410];//为了简短，代码中删去了不必要的数据读入，处理输出等部分

int lk[410];

bool find(int x)

{

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to;

if(!vis[to])

{

vis[to]=1;

if(!lk[to]||find(lk[to]))

{

lk[to]=x;

return 1;

}

return 0;

}

int n,m,ans;

int main()

{

for(int i=1;i<=n;i++)

{

memset(vis,0,sizeof(vis));

if(find(i))ans++;

}

理论

上述文字可以告诉我们匈牙利算法是怎样实现的，同时可以给我们一个关于它正确性的主观认识。然而，我们都知道，对于一个算法，（~~看不懂的~~）理论知识才是它的核心，下面蒟蒻博主尝试从另一个角度来带给大家对于匈牙利算法的另一个认识~（相关图片待补

定义

二分图：对于某无向图，若它的顶点可以划分为两个互不相交的子集，且每条边的两端点分别属于两子集，则称该图为二分图（如上 [骗分] 中图 (1)
（二分图）匹配：选择一个边集，使得任意边不存在重复的顶点，称该边集为该（二分）图的一个匹配。
极大匹配：对于一个匹配，若无法在原图中找到任意边加入匹配，则称该匹配为一个极大匹配。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边 ... 形成的路径叫交替路。
增广路：对于一条路径，从一个未匹配点出发，走交替路，终止于另一个未匹配点，则这条交替路称为增广路

解决

在这些定义中，增广路具有优越的性质：

具有奇数条边
起点和终点均为未配对点
整条路径上奇数边均不在原匹配中，偶数边均在原匹配中

根据定义和上述性质，下面的结论就是显然的了：

将一条增广路上偶数边删除匹配可以将奇数边加入匹配（该操作称作增广路的取反），新的匹配数比原匹配数大一

所以如果我们不断的重复找到一条增广路——将它取反的操作，我们就可以获得一个极大匹配！

但是，我们如何证明，这个极大匹配就是原图的最大匹配呢？想证明这个问题，等价于证明若找不到从点 A 出发的增广路，则无论从别的点出发找到多少增广路改变匹配，都无法使得 A 成功匹配~

以下仅提高不严谨的证明思路：我们假设可以找到 x，y 间的增广路，取反后可以使得 A 找到配对点，那么该点定为原图中的未配对点，且我们可以将 A 与该点配对说明 A 与该点间存在一条交替路，又因为 A，该点均为未匹配路，所以该点与点 A 间原本就存在一条增广路使得假设不成立。故我们找不到点 A 的配对点使得匹配扩大，该极大匹配一定为最大匹配辣~！

算法的执行流程是这样的：

找到一未配对点 u，从 u 为端点的边中任选一条尝试配对（令其另一端点为 v），若此时 v 未配对，则配对成功，答案更新。若点 v 已经被配对，就尝试从 v 出发“扩展”该交替路，执行递归操作，尝试找到一条增广路，若成功，对该增广路取反，即回溯更新配对关系。若失败，则尝试换一条以 u 为端点的边重复操作，直至 u 配对成功或全部尝试过为止。

对所有剩下的未配对点进行操作，直至尝试完毕所有点，找不到增广路为止，此时找到原图最大匹配~

我们可以发现，它与上述的想法有着异曲同工之妙，核心在于 尝试更改配对关系，递归回溯

同时显然的，该算法可以在有限步内结束，事实上，它的时间复杂度是最坏 \(O(nm)\) 的，在实际运行中，它的效率有时甚至可以完成对 n≤100000 数据的最大匹配... 不得不说还是非常玄学的

update：2017/06/19 然而，可以被证明的是，当我们使用 Hopcroft–Karp 算法或 dinic 算法解决二分图最大匹配问题时，时间复杂度的上界仅有\(O(n \sqrt{m})\)... 所以匈牙利算法的优势貌似大概只有极低的编程复杂度了...

至此，我们从一个更本质的角度理解了匈牙利算法，同时完成了对其正确性的证明！

奇技淫巧——时间戳优化

我们注意到，在每次寻找增广路时，都需要清空一次 vis[] 数组，这为我们带来了一个严格\(O(n^2)\) 的效率损失，显然，这是很不可以接受的，所以我们可以用一种奇技淫巧优化掉它！

优化方式是很简单的... 我们维护一个时间戳 T，对于每次寻找增广路，将 T++，在判断改点是否 vis 过时直接判断 if(vis[i]!=T) 同时在更新 vis 时这样更新：vis[i]=T 即可！

这个看似简单的奇技淫巧可以为算法带来数倍以上的常数优化...

而且它的适用范围很广，有时当我们需要多次使用匈牙利算法时，每次都需要清空 lk[] 数组，这也是很大的效率损失，然而它也可以通过时间戳优化解决，在此不给出详细做法~留做思考，将会在后面的习题中出现

关于二分图的一些其他性质

König 定理：二分图最大匹配=二分图最小点覆盖

(关于最小点覆盖：记选了一个点为覆盖了以它为端点的所有边，选择最少的点来覆盖所有的边

最大独立集=所有顶点数-最小顶点覆盖

可以这样感性认识：对于点 i，若不在最小点覆盖中，则必然未与其他点相连，若相连，则必然对应边未被覆盖，与最小顶点覆盖矛盾

二分图的最大团=补图的最大独立集

这是很好理解的，补图中互相无边相连的点在原图中定然有边相连

还能做什么

最小路径覆盖：在一个有向图中，找出最少的路径，使得这些路径经过了所有的点。（一条路径起点的入度为 0, 终点的出度为 0, 中间节点的出入度都为 1。每一个点最多只能有 1 个后继, 同时每一个点最多只能有 1 个前驱）

DAG 的最小不相交路径覆盖

(不相交即任何一个顶点有且只有一条路径与之关联

算法： 把原图的每个点 V 拆成\(V_x\) 和\(V_y\) 两个点，如果有一条有向边 A->B，那么就加边\(A_x\)−>\(B_y\)。这样就得到了一个二分图。那么最小路径覆盖=原图的结点数-新图的最大匹配数。

证明：一开始每个点都是独立的为一条路径，总共有 n 条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了 1。所以找到了几条匹配边，路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。

DAG 的最小可相交路径覆盖

算法：先用 floyd 求出原图的传递闭包，即如果 a 到 b 有路径，那么就加边 a->b。然后就转化成了最小不相交路径覆盖问题。

证明：为了连通两个点，某条路径可能经过其它路径的中间点。比如 1->3->4，2->4->5。但是如果两个点 a 和 b 是连通的，只不过中间需要经过其它的点，那么可以在这两个点之间加边，那么 a 就可以直达 b，不必经过中点的，那么就转化成了最小不相交路径覆盖。

题目

BZOJ 1854 [Scoi2010] 游戏难度 ★

暂放题意于此：

n 个武器，每个武器有两个属性，只能使用其中一个，要求选择一些武器可以造成形如 1 2 3 4 递增的伤害求最大伤害

BZOJ 1191 [HNOI2006] 超级英雄 Hero 难度 ★

暂放题意于此：

m 道问题，n 个锦囊妙计，每道题都可以从两种锦囊妙计中选择一种，每种锦囊妙计只能用一次，必须按照顺序通过每道题，求最多几道题？

BZOJ 2150 部落战争难度 ★★

暂放题意于此：

一个 01 矩阵，1 可以走，0 不可以，可以多次从任意 1 点出发，只能向下以 R*C 的方式走，问至少出发几次抵达所有 1 点 (经过的 1 点不可重复经过

BZOJ 3175 [Tjoi2013] 攻击装置难度 ★★

暂放题意于此：

一个 n*n 的 01 网格图...0 可以放装置，装置的攻击范围是马的走法... 问最多放多少个装置....

BZOJ 2744 [HEOI2012] 朋友圈难度 ★★★★

暂放题意于此：

对于 A，B 两个点集，每个点均有一个权值。对于点集 A 中的两个互异元素，记它们的权值为 (i,j)，当且仅当 (i^j)%2=1 时它们间有边相连。
对于点集 B 中的两个互异元素，记它们的权值为 (i,j)，若 (i^j)%2=0 或 (i|j) 在二进制下有奇数个 1 时它们间有边相连，此处^记为异或，|记为或，给出 A，B 集间的连接关系，求整个图的最大团...

BZOJ 1143 [CTSC2008] 祭祀 river 难度 ★★★

暂放题意于此：

在一个 DAG 上选若干点，使得点两两不互达。

部分改编自：http://www.cnblogs.com/justPassBy/p/5369930.html