二分图匹配

本文主要介绍一些二分图主流的建模，然后还有对匈牙利算法的一个拓展（俗称魔改）

什么是二分图？

显然，是二分图的图就是二分图，NM还要我来写？

最大匹配

描述：给出一个二分图，问最多能选出多少边，这些边的端点互不相同。

显然匈牙利算法可以很好地解决这个问题。

匈牙利算法：

匈牙利的核心就是增广路，又称交错路。

我们从左边的点出发，每次交替地走匹配边和未匹配边（从左向右的是未匹配边，从右用 \(link\) 走回左边的就是匹配边），最后以未匹配边结束， 就找到了一条交错路，然后将交错路上的匹配边取消匹配，未匹配边进行匹配，就对原本的匹配进行了一条边的增广。

显然，对每一个点都进行一次增广可以找出最大匹配。

最小点覆盖

描述：用选出尽可能少的点（左右不限），使得最后所有的边都至少有一个端点被选出。

我们可以得出一个很显然的结论：最小点覆盖 \(\geq\) 最大匹配 ，因为最大匹配选出的边集的端点互不相交，就意味着每一条匹配边都至少需要选出其一个端点来覆盖自身。

那么现在的问题就是需要证明它能够取等。

\(Konig\) 给出了一种构造性证明：

我们先找出最大匹配，然后，对于左边所有未匹配点，我们从其出发，只沿着交错路，将所有能够遍历到的点进行标记（不管左边还是右边）。最后左边的所有未被标记的点和右边所有被标记的点就是我们需要选出的点。

关于它的证明有两点：正确性和最优性

先是正确性：

考虑两种点。

首先是右边被标记了的点：显然，既然它被标记了，而且是从一个未匹配点出发遍历到了它，它就一定是一个匹配点（不然的话我们找到的就不是最大匹配了）。

其次是左边没有被标记的点：显然，左边被标记了的点，都是右边被标记了的点能够照顾到的（而且显然不是未匹配点就是和右边标记点匹配的点），那么，左边没有标记的点，恰好能够覆盖剩下的没有被右边的点覆盖到的边集。

所以正确性显然。

其次是最优性：

我们发现，选出来的点都是匹配点，然后，不会有一条匹配边的两个端点都被选出，所以说最后选出来的点已经就是匹配边的条数。

证毕。

好了我们现在就搞明白了最小点覆盖到底是怎么从最大匹配转换过来的了。

需要注意的是，一般图（没有给出什么特殊性质）的最小点覆盖是 \(NP\)完全问题，尚且不存在多项式时间复杂度的解法，在比赛中遇到的话实在不行就爆搜剪枝吧 \(qwq\) 。

最大独立集

描述：选出尽可能多的点，使得这些点之间两两不存在连边（相当于删去所有的边）。

我们发现，我们用点覆盖，可以覆盖所有的边，那么我们删去点覆盖，就删去了所有的边；反之，我们删去的如果不是点覆盖，那么就仍然存在有边连接着某两个点。

所以显然，我们要让独立集最大，就要让删去的点覆盖最小，那么我们取最小点覆盖的点集的补集就就可以了。

最大团

描述：选出一些点，这些点构成一张完全图（两两间都有连边）

我们发现这个玩意儿也是个 \(NP\)完全问题（\(doge\)）。

其实不是，有一种特殊情况我们可以用已有的方法解决它：当原图的补图是一个二分图时。

考虑原图的补图，上述条件就变成了：选出一些点，这些点之间两两没有连边。

于是这个问题就转化为了最大独立集的问题，可以求解。

DAG 上最小路径划分

描述：给出一个有向无环图 (\(DAG\)) ，要求用一些有向路径将所有的点覆盖，这些路径之间不能有共同的点，问路径的最少数量。

我们这里要用到一个很普遍的技巧：\(DAG\) 上拆点，将一个点拆为入点和出点，显然出点只会和入点连边，所以拆点之后的图是一张二分图。

然后我们发现，假如我们将一个点到自己视为一条路径，那么初始的时候就有 \(n\) 条路径，而我们在二分图上每选择一条边，就相当于合并了原图上的两条路径。

然后，我们如果在二分图上面跑一个最大匹配，就保证了每一条了链只覆盖了一个点——显然，每一个点最多入度为一，最多出度为一，正好对应了最大匹配上每个点只会匹配一条边。

所以最后的答案就是 \(n\) \(-\) 最大匹配。

然后这里要注意的是，为什么是 \(DAG\) 而不是说普通有向图呢？因为普通的有向图存在环，而环会导致二分图上面出现完美匹配，让你以为你能够合并 \(n\) 次，实际上你最后一次合并的是本来就被合并过的两条链。对于这种情况，可以 \(Tarjan\) 缩点解决。

DAG 上最小路径覆盖

描述：选出最少的可以相交（无论是重复点还是重复边），覆盖所有的点。

很多人在这里都遇到过这样的疑惑：为什么我不直接对 入度为 \(0\) 的点的个数 和出度为 \(0\) 的点的个数 取一个 \(\max\)。

解答：反例其实很好构造——\((1\rightarrow 2\ ,1 \rightarrow 3\ ,2\rightarrow 4\ ,3\rightarrow 4)\)，你会发现，如果你仅仅以入度和出度为 \(0\) 的点为标准那么你无法保证最后覆盖了所有的点。

好，回到这道题目，我们如何求最小路径覆盖？

这就需要用到我们图论初期的知识了：\(Floyd\) 求传递闭包！

我们先处理出每个点可以到达的点，然后直接在他们俩之间连一条边，就可以转化为最小路径划分来做了。

很好理解吧？

相当于我们对所有的路径取一个并集，然后再在这个并集上面划分（有点抽象）。

\(emmmm\) ，这么说吧，你就理解为可以传送的最小路径划分吧（传送后的路径和传送前的路径视为有新建了一条边将他们连接） 。

环的处理和路径划分一样。

DAG 上最大不可达点集

又称：反链。

描述：在选出一些点，使得这些点互相不可达。

这个问题好水，直接跑传递闭包然后跑最大独立集就阔以了啊。

理解显然。

有向环覆盖

描述：将每个点划分到一个简单有向环中，求方案。

显然，在环上说明入度和出度都是一，那么就相当于拆点的二分图上完美匹配。

拓展 Hungary

其实就是一些小技巧，但是你也知道我的习惯，喜欢给没有名字的小技巧取名字 \((doge)\) 。

拓展匈牙利也叫二次匈牙利（瞎编），由全国 \(Oier\) 在许许多多年份陆陆续续发现，可以用于解决许多需要在图上进行修改之后跑匈牙利的问题。

比如：1.必选某条边的最大匹配；2.必选某个点的最大匹配；3.最小字典序匹配；4.不选某条边的最大匹配；5.不选某个点的最大匹配。

1. 必选某条边

   先跑一遍匈牙利，得到一个最大匹配，如果这条边已经匹配了，那么就匹配了；如果这条边只有一个点是匹配的，那么直接给那个匹配点换边就行（删除一条边再添加当前边最大匹配还是最大匹配）。

   否则，对于我们选定的这条边，我们先删除左右端点原本的匹配（删除两条边），然后将这条边视为一个匹配（添加一条边），然后再对右端点匹配的左边的点进行增广，就可以得到必选某条边时的最大匹配。

2. 必选某个点

   先跑一遍匈牙利，得到一个最大匹配，如果这个点已经匹配了，那么就匹配了。

   否则，我们直接随便找一个和它直接相连的已经匹配的了的点（一定有，不然它在第一遍的时候就应该匹配了），然后换边就行。

3. 字典序最小（其实这个一般都是在完美匹配上讨论，不过普通匹配倒也无所谓）

   先跑一遍匈牙利，得到一个最大匹配；为了方便起见，我们对所有点连向的点按编号从小到达排序。

   然后从小到大讨论每一个点的匹配。

   显然，我们讨论的每一个点都有一个原配；首先，取消这个点的原配，其次，尝试对该点进行增广（一定可以增广，大不了重新去找原配），然后（因为可到点已经从小到达排序了所以字典序贪心地最小）将这个点和它的新配的匹配边锁死（即锁定新配，之后不可再访问）。

   这样我们不仅保证了每一个时刻都仍是最大匹配，还保证了字典序最小（整体复杂度同匈牙利）

4. 不选某条边的最大匹配

   同理，先跑一遍匈牙利，得到一个最大匹配，如果这个边没有被选，则没有被选。

   否则，断开并将这条边加入不可访问名单，然后对左端点进行增广。

5. 不选某个点的最大匹配

   将不选的些点放到右边，然后跑一遍匈牙利，对于一个点，如果它已经没有被选，那就没有被选。

   否则，断掉这个点的所有边，同时锁死这个点，然后对这个点原本匹配的点进行增广。

好的，这就是一些常见的拓展问题的总结。

我们会发现拓展匈牙利的核心思想就是充分利用原有信息，先跑一遍匈牙利然后再在一次增广的时间复杂度内进行 修正。

然后为了方便操作，其实还有一种方法可以让你直接用一份 \(DFS\) 的代码对任意一个点进行增广，你直接同时维护左边的点对右边的点的匹配就可以了。

二分图博弈

看着儿，有人，叫我新开专题。我懒，真的，我单知道二分图可以拿来匹配，却没有想到它可以用于博弈。

好了不说废话了。

描述：给出一张二分图，有两个人在 \(van\) \(2p\) （博弈），请你求出哪些点先手必胜。

结论：所有一定在最大匹配上的点先手必胜。

证明显然：

考虑一种策略：先手每次都走匹配边，后手每次就只能走未匹配边。

分两种情况讨论：匹配边比未匹配边多一条：此时先手必胜

否则：匹配边和未匹配边数量相同，此时后手必胜。但是，如果匹配边和未匹配边数量相同，则交换匹配边，仍然是一个最大匹配，与条件“最大匹配唯一”矛盾，故不存在该情况。

所以这些点先手必胜。

那么为什么不是这些点先手就不必胜了呢？

显然，我们可以找到一种匹配使得这个点没有被匹配，然后我们先手随便走一条边都是未匹配边，然后接下来后手可以走匹配边，然后我们就输了。

于是证完了。

Hall 定理

离谱，看了一眼去年 PKU 的题目，撸猫 要用到 Hall 定理，那好吧，就搞一搞霍尔定理吧。

先考虑普通的二分图 \((V1,V2,E)\) ,其存在完美匹配当且仅当 \(S\subseteq V2(or\ V1)\)，都有 \(N(S)\ge |S|\)，其中 \(N(S)\) 表示与 \(S\) 相邻的点的个数。

下面考虑简要证明：

充分性：显然，完美匹配中每一个点都有与之匹配的点，那么一个点集自然 \(N(S)\ge |S|\)。

必要性：我懒得写了，但主要的思路就是假设最大匹配且不满配然后找饱和点和增光路来反证

好的，有了这些之后，我们就可以搞一些拓展了。

比如说加入源点和汇点，\(V2\) 中所有点向汇点连边，带流量限制。

那么把 \(N(S)\) 改成 和 \(S\) 中有点相连的点的最大入流之和，\(|S|\) 改成 \(S\) 的出流，就可以套用上面的结论了。

顺带一提，为什么 \(N(S)\) 不等于所有点的度数之和？

显然（Clear Cut）一个点可能连多个点（You Evil Predefine）。