二分图

最大匹配

最基本的东西，可以用 dinic 在 \(\mathcal{O}(m\sqrt n)\) 的时间内解决。

Hall 定理

判断二分图是否存在完美匹配的定理。

默认左部点数小于等于右部点数，定义 \(N(S)\) 为左部点中在 \(S\) 中的点相连的右部点的并集，如果 \(\forall S,|N(S)|\ge |S|\) 则二分图存在完美匹配。

最小点覆盖

最小点覆盖等于最大匹配。

首先最小点覆盖肯定大于等于最大匹配，因为匹配边的两点必然选一个。

然后我们可以构造一组等于最大匹配的最小点覆盖：

一开始匹配边长这样，假设我们一开始选择全部左边的匹配点，显然是不行的，考虑调整。

我们想让最上面那个非匹配边被覆盖，我们可以不选左边的匹配点了，改成选右边的匹配点就可以了。

所以我们证明了最小点覆盖等于最大匹配。

上面的构造方法也告诉了我们构造方案的做法，具体实现是：

1. 找到左边的非匹配点开始非匹配边、匹配边交替走，一直走到没路走，标记已经经过的结点，注意不能经过已经标记过的节点。
2. 最小点覆盖就是左边的未标记点加上右边的标记点。

void dfs(int now) {
	vis[now] = true;
	int SIZ = v[now].size();
	for(int i = 0; i < SIZ; i++) {
		int next = v[now][i].to;
		if(vis[next] || !v[now][i].val)//正向边的容量为0说明是匹配边，反向边的容量为0说明是非匹配边
			continue;
		dfs(next);
	}
}

最大独立集

对于一个点覆盖，一条边两端至少有一个点，对于它的补集，一条边最多有一个点，所以它的补集是一个独立集。

对于一个独立集，同理补集是一个点覆盖。

所以独立集与点覆盖一一对应，所以最大独立集等于点数减去最小点覆盖。

最小链覆盖

对于一个 \(n\) 个节点的 DAG，我们可以对应出一个 \(2n\) 个节点的二分图，一个原图的点 \(u\) 拆成 \(u_l,u_r\)，原图的一条边 \((u,v)\) 变成 \(u_l\to v_r\)。

我们发现 \(n\) 减去这个二分图的最大匹配就是最小链覆盖，因为一开始我们把每一个点当成一条链，二分图上每匹配一次相当于把两条链首尾相接，于是链减少了一条。

而最大匹配等于最小点覆盖等于 \(2n\) 减去最大独立集，所以原图的最小链覆盖加 \(n\) 就是二分图的最大独立集。

最长反链

这里只研究是偏序集的情况。

dilworth 定理就是最小链覆盖等于最长反链。

首先最小链覆盖肯定大于等于最长反链，因为最长反链上的每一个点都不在同一条链上。

下面归纳证明最小链覆盖等于最长反链，首先 \(n=1\) 时命题成立。

对于 \(n>1\) 我们取出点集中的极大元 \(x\)，它肯定没有出边，且取出之后的图 \(G'\) 满足最小链覆盖等于最长反链。假设 \(G'\) 中最小链覆盖有 \(k\) 条链，那么最长反链也有 \(k\) 个点。

首先显然我们可以随便取一组最小链覆盖，那么对于任意的最长反链，它的 \(k\) 个点肯定在每一条链上恰好一个，因为反链上的两个点不能在同一条联赛上。发现如果我们把每一条链上的极大元取出来，这就是一组最长反链，因为如果链 A 的极大元有边连往链 B 的极大元，那么链 A 的全部点都会向链 B 的极大元连边，与链 A 必然会选一个矛盾。

设这些最大值组成的集合为 B，显然加入 \(x\) 后最小链覆盖和最长反链都增加不超过 1。

1. B 中所有元素都没有向 \(x\) 连边，那么 B 可以直接加入 \(x\)，所以最小链覆盖小于等于最长反链，又因为大于等于，所以等于。
2. B 中有元素向 \(x\) 连边，那么 \(x\) 可以加入那条链，所以最小链不增加，所以证出小于等于，所以等于。

所以就证完了，总结一下就是对于一个 \(n\) 个点的偏序集：最长反链=最小链覆盖=n-对应的二分图的最大匹配=n-对应的二分图的最小点覆盖=n+对应的二分图的最大独立集。