二分图
**二分图：**又称作二部图，是图论中的一种特殊模型。 设 $G=(V,E)$ 是一个无向图，如果顶点 $V$ 可分割为两个互不相交的子集 $(A,B)$，并且图中的每条边所关联的两个顶点 $i$ 和 $j$ 分别属于这两个不同的顶点集 $(i∈A, j∈B)$，则称图 G 为一个二分图。
简单来说，如果图中所有顶点可以被分为两个集合，图中所有的边的头和尾不属于同一个顶点集合，而是跨越两个集合，则这个图是一个二分图。
例如：图 1.1 所示的图，无论如何划分顶点集合，也不能保证所有边的头和尾隶属于不同集合，因此，图 1.1 所示的图不是二分图。
图 1.1
例如：图 1.2 所示的无向图：
图1.2
将顶点 $a，b，c，d$ 作为集合 $A$，将 $e，f，g，h$ 作为集合 $B$，将图 1.2 转化为图 1.3 所示：
图 1.3
可以看出，图中顶点可以划分为 $A，B$ 两个集合，而任意一条边的头和尾又分别隶属于集合 $A$ 和集合 $B$，因此，此图为二分图。
**匹配：**在图论中，一个匹配（matching）是指一个边的集合，其中任意两条边都没有公共顶点。 例如：图 2.1 中红色的边，可以为图 1.3 所示图的一个匹配。
图2.1
**最大匹配：**一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。图 3.1 是一个最大匹配，它包含 4 条匹配边。
图 3.1
**完美匹配：**如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突），但并非每个图都存在完美匹配。
**交替路径：**从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边… 形成的路径称为交替路径。
增广路径：从一个未匹配点出发，走交替路径，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路径（agumenting path）。
**匈牙利算法：**利用增广路径求二分图的最大匹配算法称作匈牙利算法。（匈牙利数学家 Edmonds 于 1965 年提出）。
**基本思想：**通过寻找增广路径，把增广路径中的匹配边和非匹配边的相互交换，这样就会多出一条匹配边，直到找不到增广路径为止。
例如：以图 2.1 所示的二分图为例，使用匈牙利算法求解图的最大匹配。 （1）从顶点 $a$ 出发，按照交替路径前进，第一个非匹配边为，到达顶点 $e$，$e$ 为非匹配点，构成增广路径。令 $a \to e$ 为匹配边，顶点 $a$，$e$ 为匹配顶点。
（2）从顶点 $b$ 出发，第一非匹配边为 $e$，到达顶点 $e$，选择匹配边到达 $a$，选择非匹配边，$g$ 为非匹配点，找到一条增广路径。
（3）交换增广路径中的匹配边与非匹配边，得到如下匹配。
（4）从顶点 $c$ 出发，第一非匹配边为 $e$，到达顶点 $e$，然后按照交替路径前进，到达顶点 $b$，无法继续前进。
（5）从顶点 $c$ 出发，选择第二条非匹配边。
（6）从顶点 $d$ 出发，选择非匹配边，到达顶点 $g$，选择匹配边，到达顶点 a，选择非匹配边到达顶点 $e$，选择匹配边，到达顶部 $b$，没有可以选择的边，且没有找到增广路径。
（7）继续从顶点 $d$ 出发，选择非匹配边，找到增广路径，将边变为匹配边，算法结束。
匈牙利算法多用于指派问题中，例如任务匹配问题。通过转化为二分图的形式，求解最大匹配，保证实现最优分配。
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 <= M; ++i)
{
memset(vis, 0, sizeof(vis)); //重置vis数组
if (match(i))
cnt++;
}
return cnt;
}