1 基础概念

二分图的概念在网络流学习中其实已经有所涉及。具体来讲，二分图就是节点由两个集合组成，且两个点集内部没有边的图。

那么二分图有以下经典性质：二分图中没有奇环。

证明显然。由于每一次走边一定是从一个点集走到另一个点集，如果要回到当前点集，那么必须要走偶数条边，因此二分图中没有奇环。

那么我们就可以以此来判定一张图是不是二分图，也就是说我们对整张图进行遍历，如果找到奇环则说明不是二分图，否则就是。

2 二分图最大匹配

2.1 问题概述

给定一张二分图 \(G\)，要求选出一些边，使得边之间没有公共端点，且边的数量最大。这类问题就是二分图最大匹配问题。

具体来讲有下面两种常用做法。

2.2 匈牙利算法

2.2.1 增广路

二分图中的增广路与网络流中的有一些相似之处，两者都是通过找出一条新的路径来让答案变的更优。

我们假设我们已经找出了一组合法的匹配。此时有一些点是匹配点，有一些是非匹配点。考虑进行一个如下操作：从一个非匹配点开始，按照非匹配边 - 匹配边 - 非匹配边 - 匹配边 - …… - 非匹配边的路径走下去，此时一定走了奇数条边，且其中非匹配边的数量比匹配边数量多 \(1\)。这个时候我们将所有匹配边换成非匹配边，而将非匹配边换成匹配边，我们发现我们的匹配数增加了 \(1\)。那么这条路径就是所谓的增广路。

所以我们只需要按照这种方式不断找增广路更新即可。如果需要记录每个右部点对应的匹配点，那么在增广路上进行取反操作的时候更新即可。

代码如下：

int mth[Maxn], vis[Maxn];
//右部点的匹配点，访问标记
bool dfs(int x) {
	for(int i = head[x]; i; i = edge[i].nxt) {
		int to = edge[i].to;
		if(vis[to]) continue;//to 不在增广路上
		vis[to] = 1;//走到 to
		if(!mth[to] || dfs(mth[to])) {//走匹配边到另一边的节点
			mth[to] = x;//更新匹配点
			return 1;
		}
	}
	return 0;
}

int main() {
	int ans = 0;
	for(int i = 1; i <= n; i++) {//遍历每一个未匹配点
		for(int j = 1; j <= n; j++) vis[j] = 0;
		if(dfs(i)) ans++;//如果找到一条增广路，答案加一
	}
	cout << ans;
	return 0;
}

2.2.2 另一种理解

其实对于增广路算法更广泛的理解是这一种……本质上和增广路是一样的。

考虑现在我们要将 \(i\) 这个左部点加入到匹配中，那么我们就要找一个对应的右部点与之匹配。如果找到一个右部点没有匹配点，直接匹配即可。否则，我们考虑这个右部点原先对应的匹配点 \(j\)，此时 \(j\) 就需要重新找一个右部点与之匹配。这就和 \(i\) 的情况一样了，递归处理即可。

那么代码和上面一样，对应注释有一些区别：

int mth[Maxn], vis[Maxn];
//右部点的匹配点，访问标记
bool dfs(int x) {
	for(int i = head[x]; i; i = edge[i].nxt) {
		int to = edge[i].to;
		if(vis[to]) continue;//to 是一个待匹配的右部点
		vis[to] = 1;//标记 to 是准备和 x 匹配的
		if(!mth[to] || dfs(mth[to])) {
        //可以直接匹配    看对应匹配点能否重新匹配
			mth[to] = x;//更新匹配点
			return 1;//返回该点可以重新匹配
		}
	}
	return 0;
}

int main() {
	int ans = 0;
	for(int i = 1; i <= n; i++) {//遍历每一个未匹配点
		for(int j = 1; j <= n; j++) vis[j] = 0;
		if(dfs(i)) ans++;//如果该点可以加入到匹配中，答案加一
	}
	cout << ans;
	return 0;
}

容易发现，我们对每一个点都要遍历一次，单次遍历复杂度 \(O(m)\)，总复杂度 \(O(nm)\)。

2.3 网络流

实际上最大匹配可以转化为最大流简单求解。具体的，我们认为每一条边是左部点连向右部点，流量为 \(1\)。同时建立超源超汇，从超源向左部点连流量为 \(1\) 的边，从右部点向超汇连流量为 \(1\) 的边。那么最大流自然就是最大匹配。

使用 Dinic 算法求最大流可以做到 \(O(\sqrt nm)\) 求解，理论上是比匈牙利算法优的。

2.4 应用

2.4.1 朴素最大匹配

我们看一道例题：[ZOJ1654]放置机器人。

我们对于每一行的联通块进行标号，再对每一列的联通块进行标号。对于每一个空白格子，将他在行上所属联通块与他在列上所属联通块之间连边。容易发现这一定构成了二分图，并且每一条边恰对应一个机器人。由于要求机器人之间不能互相攻击，所以同一个联通块内只能放一个机器人，也就是说每一个点都只能由一条匹配边与之相连。容易发现这就是二分图最大匹配问题，简单求解即可。

2.4.2 最小点覆盖

最小点覆盖是这样一类问题：

给出一张二分图，选出一些点，使得每一条边至少有一个端点被选，求最少的点数。

那么和以往所学的其他定理类似，我们有 König 定理：最小点覆盖 = 最大匹配。证明见此。

这里我们同样看一道例题：[poj2226]Muddy Fields。

发现此题与上面的题要求类似，按照同样方式建边。同样的可以得到每一条边对应一块泥地，每一个点对应一块木板。现在的要求是对于每一条边，至少在它的两个端点中选一个点进行覆盖。显然这是最小点覆盖问题。又由于最小点覆盖等于最大匹配，所以此题代码与上一题几乎是一模一样的。

2.4.3 最大独立集

最大独立集是这样一类问题：

给出一张二分图，选出一些点，满足没有两个点之间有连边，求最大的点数。

考虑上面我们选出了最小点覆盖，那么将剩下的点全部选上一定就是最大独立集。这个证明较为简单。

考虑如果剩下的点全部选上有两个点之间有连边，那么这条边在最小点覆盖中一定没有任何一个端点被选中，这与条件矛盾。因此剩下的点全部选上就是最大独立集。

也就是说，最大独立集 = \(n\ -\) 最小点覆盖。

我们再看最后一道例题：[HZOI 2016]猫和狗。

我们将观众按照爱猫和爱狗分为两类，然后在两边找出两个点，使得他们当中一个喜欢的与另一个不喜欢的编号一致，将这两者连边。此时所有连上边的两个端点都不能同时选，而我们要求选的点最多，显然就是最大独立集了。

综上不难看出，二分图的基本算法并不复杂，与网络流一致，其关键点还是在于建图。将图论模型建立出来以后问题就引刃而解了。