二分图
二分图相关内容。
什么是二分图
二分图是一种特殊的图。
二分图的一个性质是，节点由两个集合组成，且两个集合的内部没有任何一条边。
换而言之，就是我们可以将二分图的两个集合中的所有节点分别染成两种不同的颜色（比如红色与蓝色），可以发现任意一条边都连接着两个不同颜色的点。
我们一般将二分图的两个集合分别放在我们的左边和右边，而边都是横向的。（其实你分别叫这两个集合华约和北约也没人抗议）
我们如何判断一个图是二分图？
根据二分图的定义，我们可以推断出来一个重要的定理：
二分图没有奇数环。
因为一个二分图的所有边都是横跨两个集合的，每次需要横跨偶数次才能回到起点所在的集合，故二分图没有奇数环。
我们可以利用这个性质对给定的图进行搜索，如果找到了奇数环，那么这个图就一定不是二分图，反之亦然。
已知所有二分图相关的问题应该都可以通过转化成为网络流问题来求解，所以在这里我就不对传统的二分图相关算法进行讲解，如匈牙利算法。
二分图有关的问题见下面：
二分图最大匹配
啥是最大匹配？
“任意两条边都没有公共端点”的边的集合被称为图的一组匹配。
在二分图中，包含变数最多的一组匹配被称为二分图的最大匹配。
对于任意一组匹配 $E$ ，属于 $E$ 的边被称为匹配边，不属于 $E$ 的边被称为非匹配边。匹配边的端点被称为匹配点，其他店被称为非匹配点。
增广路
如果在二分图中存在一条连接两个非匹配点的路径 $path$，使得非匹配边与匹配边在 $path$ 上交替出现，那么我们称 $path$ 是 匹配 $E$ 的一条增广路，也称交错路。
增广路具有以下性质：
- 长度为奇数。
- 路径上第奇数条边是非匹配边，第偶数条边是匹配边。
利用以上性质，我们尝试将路径上所有边的状态取反，也就是原来的匹配边变成了非匹配边，原来的非匹配边变成了匹配边。
经过了这样的一个操作，我们新得到的边集 $E’$ 仍然是一组匹配，且匹配边的数量增加了1。
利用这样的一个操作，我们可以得到一个推论：
二分图的一组匹配 $E$ 是最大匹配，当且仅当图中不存在 $E$ 的增广路。
注意：这里的增广路与网络流中的增广路概念不同。
求解
我们可以使用匈牙利算法，一种利用增广路来求解的算法。其时间复杂度为 $O(nm)$ 。
但是，我们可以使用Dinic来求解。Dinic比匈牙利算法要快（时间复杂度为 $O(m\sqrt{n})$），而且适用范围较匈牙利算法更广。
对于这样的一个问题，我们只需要将所有左边的点华约成员国与源点苏联连一条容量为1的边，再将所有右边的点北约成员国与汇点美国连一条容量为1的边。最后，把所有的原图中的边变为一条容量为1的边。
这张图的最大流就是原图的最大匹配数。
以Luogu P3386 【模板】二分图最大匹配为例。
示例代码：Luogu P3386
与二分图最大匹配相关的概念
二分图最大独立集
从图中选择最多的点，满足两两之间没有边相连。
在二分图中，这个就是去掉最大匹配后的剩余部分。
二分图最小点覆盖
从图中选择最少的点，满足每条边至少有一个端点被选上。
我们不难发现，点覆盖的补集其实是独立集。
在二分图中，最小点覆盖就是去掉最大独立集后的剩余部分，与最大匹配重合。
二分图最大权匹配
如果我们给二分图上的边加上边权的话，我们就可以求边权和最大的匹配了。
实现
我们可以将其转换为费用流模型，将其按照最大匹配的建图方式建图，并给其中跨集合的边加上一个费用，求这个图的最大费用最大流。