题目来源：华为机试题
内容来源：https://zhuanlan.zhihu.com/p/96229700

1. 问题

二分图（Bipartite graph）是一类特殊的图，它可以被划分为两个部分，每个部分内的点互不相连。下图是典型的二分图。

在上面的二分图中，每条边的端点都分别处于点集X和Y中。匈牙利算法主要用来解决两个问题：求二分图的最大匹配数和最小点覆盖数

1.1 最大匹配问题

现在Boys和Girls分别是两个点集，里面的点分别是男生和女生，边表示他们之间存在“暧昧关系”。最大匹配问题相当于，假如你是红娘，可以撮合任何一对有暧昧关系的男女，那么你最多能成全多少对情侣？（数学表述：在二分图中最多能找到多少条没有公共端点的边）

算法：
我们从B1看起（男女平等，从女生这边看起也是可以的），他与G2有暧昧，那我们就先暂时把他与G2连接（注意这时只是你作为一个红娘在纸上构想，你没有真正行动，此时的安排都是暂时的）。

来看B2，B2也喜欢G2，这时G2已经“名花有主”了（虽然只是我们设想的），那怎么办呢？我们倒回去看G2目前被安排的男友，是B1，B1有没有别的选项呢？有，G4，G4还没有被安排，那我们就给B1安排上G4。

然后B3，B3直接配上G1就好了，这没什么问题。至于B4，他只钟情于G4，G4目前配的是B1。B1除了G4还可以选G2，但是呢，如果B1选了G2，G2的原配B2就没得选了。我们绕了一大圈，发现B4只能注定单身了，可怜。（其实从来没被考虑过的G3更可怜）

这就是匈牙利算法的流程。说白了就是递归，不断往上找。

1.2 相关原理

最小点覆盖问题
另外一个关于二分图的问题是求最小点覆盖：我们想找到最少的一些点，使二分图所有的边都至少有一个端点在这些点之中。倒过来说就是，删除包含这些点的边，可以删掉所有边。

定理：
一个二分图中的最大匹配数等于这个图中的最小点覆盖数

2. 应用

1. 洛谷P1129 矩阵游戏

链接：洛谷
小 Q 是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个n×n 黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：

• 行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）。
• 列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）。

游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。
对于某些关卡，小 Q 百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！于是小 Q 决定写一个程序来判断这些关卡是否有解。

转化：
我们把矩阵转化为二分图（左侧集合代表各行，右侧集合代表各列，某位置为1则该行和该列之间有边）。我们想进行一系列交换操作，使得X1连上Y1，X2连上Y2，……
大家可以想象，所谓的交换，是不是可以等价为重命名？我们可以在保持当前二分图结构不变的情况下，把右侧点的编号进行改变，这与交换的效果是一样的。
我们把矩阵转化为二分图（左侧集合代表各行，右侧集合代表各列，某位置为1则该行和该列之间有边）。我们想进行一系列交换操作，使得X1连上Y1，X2连上Y2，……
大家可以想象，所谓的交换，是不是可以等价为重命名？我们可以在保持当前二分图结构不变的情况下，把右侧点的编号进行改变，这与交换的效果是一样的。所以想让X1、X2…与Y1、Y2…一一对应，其实只需要原图最大匹配数为4就行了

2. vijos CoVH之柯南开锁

链接：vijos
算法：
如果我们把样例的矩阵，转化为二分图的形式，是这样的：

按下一行或一列，其实就是删掉与某个点相连的所有边。现在要求最少的操作次数，想想看，这不就是求最小点覆盖数吗？所以直接套匈牙利算法即可

3. TYVJ 棋盘覆盖

题目：
描述 Description

• 给出一张nn(n<=100)的国际象棋棋盘，其中被删除了一些点，问可以使用多少12的多米诺骨牌进行掩盖。

输入格式 Input Format

• 第一行为n，m（表示有m个删除的格子）
• 第二行到m+1行为x,y，分别表示删除格子所在的位置
• x为第x行
• y为第y列

输出格式 Output Format

• 一个数，即最大覆盖格数

算法：
经典的多米诺覆盖问题大家都很熟悉，我们把棋盘染色，每个多米诺骨牌恰好覆盖一个白格和一个黑格（这里为了美观染成了其他颜色，下面仍将其称作黑格）。

我们删除了一些格子：

现在要求多米诺骨牌最大覆盖数。
你可能已经看出来了，我们在染色之后，黑格和白格可以构成一个二分图，每个白格都只和黑格相连，每个黑格也只和白格相连。在给所有黑格和白格编号后，我们把每个未删除的格子都与它上下左右紧邻的未删除的格子相连。很显然，这张二分图的最大匹配数，就是我们能放下最多的多米诺骨牌数。注意因为数据范围较大，要用邻接表存图。
只能往非空格子填写