把 gm 开的链接阿克之后想现在洛谷做几道紫的二分图的题，但是一看有好多道，根本不知道做哪道（全做是不可能的，zyq这么懒）

如果有 dalao 看见了这篇 blog，可以推荐几道比较有意思的二分图的题吗？提前致谢 + %%%（PS:A了之后会更新的）

其实周六刚学二分图匹配的时候有一点点懵，这两天（闲着没事）就做了一点点题后，才建立了一些概念。

想着好不容易阿克了，就整点活呗，于是就有了这篇blog（zyq时隔一年终于又阿克链接了（一年前学的应该是选择结构吧））

（艹，这篇blog是用流量写的）

致歉

有些概念，笔者无法用自己有限的数理知识进行严谨的证明，只能一个较为抽象的图形进行呈现

且在预习，学习，联系二分图的过程中，难免借鉴了一些书籍，资料，暂且无法一一列举，再次致歉。

概念

二分图是一个可以把点分为两个互不相交的子集的无向图。
大概就是这样

判断一个图是否是二分图的标准

首先这个图必须有两个结点以及上，

其次，这个图里面的每个回路必须有偶数条无向边。

第一点很好证明，那么第二点呢？

我们需要将这个图在脑袋里面抽象一下。（其实是笔者不会做GIF,就这能这么抽象了）

以下图举例，选择一些点，翻折一下

就变成了这样

但如果是奇回路呢？
发现如何翻折都是

本身

二分图怎么用

我们可以在一个二分图中，求其的最大匹配，最小点覆盖，最大独立集

最大匹配

二分图的匹配是二分图的一个子集，该子集中没有一个点被重复连边。那么最大匹配就是边数最多的情况了。
对于最大匹配，首先需要了解一下增广路径

什么是增广路径呢？

增广路径的定义：设M为二分图G已匹配边的集合，若P是图G中一条连通两个未匹配顶点的路径（P的起点在X部，终点在Y部，反之亦可），并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。___by gm

ps:增广路径中起点和终点都必须没有匹配边，且处于不同集合

下图就是一条增广路径。（黑线为原匹配的边）

那么，在发现一条增广路径之后，我们将其取反，那么我们的边数就可以加一了。

（笔者在刚学二分图匹配的时候，听到这就有了亿点点疑问。如果我们取反了，那么这还可以构成匹配吗？答案是肯定的。起点和终点上没有匹配边，取反后不会对其造成影响，其他点因为已经形成了匹配，取反后也只会有一边与其相连，所以我们取反后，匹配依旧是成立的。这也就是为什么起点与终点一定要是没有匹配边与其相连）

代码实现

bool vis[maxn * maxn]; //这个点是否访问过
int match[maxn * maxn]; //走向哪个点
bool dfs(int u){
	for(int i = head[u]; i ; i = Next[i]){
		int v = tail[i];
		if(!vis[v]){
			vis[v] = 1;
			if(!match[v] || dfs(match[v])){//有增广路
				match[v] = u;  //取反
				return 1;
			}
		}
	}
	return 0;
}

int ans;

void Hungarian(){
	ans = 0;
	memset(match, 0, sizeof(match));
	for(int i = 1; i <= n; i ++){
		memset(vis, 0, sizeof(vis));
		if(!match[i])ans += dfs(i);
	}
}

最小点覆盖

点覆盖，及每一条边都至少有一个顶点被选中。根据König定理，二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数。

gm 在上课已经证明了这一点，同时matrix67大巨佬也证了这一点

所以在求最小点覆盖的时候可以用最大匹配的代码啦~

最大独立集

独立集，就是二分图中任意边都不相连的子集。

首先抛出一个结论：G的最大独立集的大小等于n减去最大匹配数。

因为最大匹配数等于最小点覆盖数，所以这些点就可以覆盖所有的边。

即去掉这些点后，任一点之间不在有边。那么G的最大独立集的大小等于n减去最大匹配数。

何时会用二分图（按不同的建图方式分类）

奇技淫巧