有正能量的分图二

帽帽猫？

二分图的判定

根据二分图的定义，只需要在图中找奇环即可。

可以使用 \(\text{BFS}\) 或 \(\text{DFS}\) 进行二分图染色实现。带权并查集或者扩展域并查集也可以直接求解。

匈牙利算法

最暴力求解二分图最大匹配的算法。

核心思想是每次加入新点时，从该点出发，找到一条匹配边和未匹配边交替，且两端均为未匹配边的路径，然后把这条路径整体的匹配状态进行翻转，得到匹配数 \(+1\) 的效果，称为增广路。

单次加入一个点时最坏会将整个图遍历一遍，所以总复杂度为 \(O(nm)\)。

默写作业：

int link[maxn];
bool vis[maxn];
vector<int> e[maxn];

bool hung(int u){
	for(int v:e[u]){
		if(!vis[v]){
			vis[v]=1;
			if(!link[v]||hung(link[v])){
				link[v]=u;
				return 1;
			}
		}
	}
	return 0;
}

我错了，这个模板过不了编译，要把所有的 link 都换成 lk 才行，我再也不在代码里面写关键字了呜呜呜。

卡满上界的构造方法

如果不加以任何优化，完全二分图就可以把该算法卡到 \(O(n^3)\) 的复杂度，但大概还是带 \(\frac 1 8\) 的常数。

小优化

• 选择非 \(0\) 度点数量较小的一侧作为最外层加入点的一侧。

• 清空 vis 数组的时候可以采用时间戳优化。

• 在算法开始之前，随机打乱加入点的顺序和每个点的出边顺序。

大优化

考虑使用 \(\text{BFS}\) 结合 bitset 进行优化。

不使用 \(\text{DFS}\) 的原因是递归时会修改 vis 数组，导致每次循环都需要重新更新有效的边集，常数过大。

int lk[maxn],prea[maxn],preb[maxn];
bitset<maxn> e[maxn],vis,now;
queue<int> q;

bool hung(int st){
	int cur=0;
	vis.set();
	while(!q.empty()) q.pop();
	q.push(st);
	while(!q.empty()&&!cur){
		int u=q.front();q.pop();
		now=(vis&e[u]);
		for(int v=now._Find_first();v<=n<<1;v=now._Find_next(v)){
			vis[v]=0;
			if(!lk[v]){
				lk[v]=cur=u;
				break;
			}
			prea[lk[v]]=u;
			preb[lk[v]]=v;
			q.push(lk[v]);
		}
	}
	if(!cur) return 0;
	for(int i=cur;i!=st;i=prea[i]) lk[preb[i]]=prea[i];
	return 1;
}

因为 bitset._Find_First() 和 bitset._Find_next() 这两个函数单次调用的最坏复杂度是 \(O(\frac n w)\) 的，但是遍历一遍容器中的所有 \(1\) 的总复杂度均摊仍为 \(O(\frac n w)\)。

所以找一次增广路的复杂度为 \(O(\frac {n^2} w)\)，总复杂度为 \(O(\frac {n^3} w)\)。

网络流求解最大匹配

对于二分图，可以把中间的边都看作是流量为 \(1\) 的由左边流向右边的边。

然后建立源点 \(S\) 并对所有左部点连流量为 \(1\) 的边。建立汇点 \(T\)，并从所有的右部点向 \(T\) 连流量为 \(1\) 的边。

那么原最大匹配问题就被转化为了最大流问题。

最小点覆盖

首先由 \(\text{Kong}\) 定理可以得到二分图的最小点覆盖 \(=\) 最大匹配。下面进行证明，令二分图的最大匹配为 \(p\)，最小点覆盖为 \(q\)。

要证 \(q=p\)，分两步证明 \(q \geq p\) 和 \(q \leq p\) 即可。

• \(q \geq p\)

对于最大匹配中的每一条边，都需要一个对应的点进行覆盖，所以至少需要 \(p\) 个点。

• \(q \leq p\)

考虑构造一种恰好 \(p\) 个点的最小点覆盖方案，由最优性即可推出 \(q \leq p\)。

将最大匹配中所有匹配边的两个端点都染成蓝色，那么显然有任意的一条边都至少存在一个端点是蓝点，尝试选 \(p\) 个蓝点来覆盖所有边。

考虑从左部的每一个未盖点出发，进行找增广路的过程，并标记访问过的点。

根据搜索过程，容易发现对于一对匹配点 \((u,v)\)，若其中有一个点被标记，则另一个点一定也被标记。

换句话说，对于一条匹配边上的两个点，要么都被标记，要么都不被标记。

同时，对于一个左部点 \(u\)，若其被标记，则所有与之相连的右部点都会被标记。

因为右部的标记点一定是匹配点，否则就会出现增广路，那么选取右部的标记点，对应的是那些两个端点均被覆盖的匹配边。

再选取左部的未标记点，对应的是那些两个端点均未被覆盖的匹配边。

这时点集大小恰好为 \(p\)，还没被覆盖的边只可能是左部标记点和右部未标记点的连边，根据上文得出不可能存在这样的边，故这是一个合法的点覆盖集。

所以有 \(q \leq p\)。

根据该定理和证明过程我们可以直接解决最小点覆盖的求解和输出方案，例题有 \(\text{UVA11419}\)。

最小边覆盖

选最少的边，使得每个点都有相邻的边被选择。

结论是最小边覆盖 \(=\) \(n_1+n_2-\) 最大匹配，其中 \(n_1\) 和 \(n_2\) 表示两部分的点数。

证明可以考虑对于一个边覆盖的方案，可以对每个点进行钦定被哪条边所覆盖，然后去掉那些不被任何一个点所钦定的边，令 \(p\) 为同时被两个点所钦定的边，就得到了答案集合大小为 \(n_1+n_2-p\) 的覆盖方案。

从这个式子出发，需要找到 \(p\) 的最大值，不难得出 \(p_{\max}\) 就是二分图最大匹配。

（稍微有点感性。）

证明：最小边覆盖 \(\geq\) 最大匹配

令最大匹配为 \(p\)，即证明 \(n_1+n_2-p \geq p\)。

因为 \(p \leq \min(n_1,n_2)\)，所以有 \(2p \leq 2 \min(n_1,n_2) \leq n_1+n_2\)，当且仅当原二分图存在完美匹配时等号成立。

构造方案

先选定最大匹配中的边，然后对于每一个未盖点再任选一条相邻边即可。

边支配集

选最少的边，使得每一条未选边都存在一条已选边和它有公共顶点。

证明：最小边支配集 \(\leq\) 最大匹配

根据最大匹配的最优性，最大匹配中的边集显然是一个合法的边支配集，得证。。。

该问题在二分图上是 \(\text{NP-hard}\) 问题：

最大独立集

不难发现，任意独立集的补集一定是一个合法的点覆盖，所以有最大独立集 \(=\) \(n_1+n_2-\) 最小点覆盖。

\(\text{DAG}\) 最小不可重路径覆盖

先钦定每个点为单独的一条路径，然后选定 \(k\) 条边组成若干条不交的路径，答案即为 \(n-k\)。

因为点不可重，所以仅保留选定的边，每个点的入度和出度都不超过 \(1\)。

考虑拆点，将点 \(i\) 拆成 \(i_1\) 和 \(i_2\) 分别表示出点和入点，对于原图中一条边 \((u,v)\)，映射到新图中的 \((u_1,v_2)\)。

在新图中跑二分图最大匹配的结果即为最大的 \(k\)，当然，这一步可以使用网络流获得更优的复杂度。

例题在这里，这道题还结合了一点 \(\text{DP}\)。

\(\text{DAG}\) 最小可重路径覆盖

允许重复经过点可以看作是允许跨越一些点。

转化为在原 \(\text{DAG}\) 上跑传递闭包之后得到的新 \(\text{DAG}\) 上求解最小不可重路径覆盖即可。

网络流解法

注意到朴素的转化方式避开不了 \(\text{Floyd}\) 求传递闭包，那么预处理部分就至少会有 \(O(\frac {n^3} w)\) 的复杂度，且二分图边数会来到 \(O(n^2)\) 级别。

考虑结合网络流技巧，在原 \(\text{DAG}\) 转化后的二分图上加上一些边，再跑最大流，以此来达成 \(\text{Floyd}\) 的效果。

若原图中有边 \((u,v)\)，这意味着 \(u\) 需要和所有 \(v\) 能到达的点连边，在二分图上仅需要添加一条从 \(v_2\) 到 \(v_1\)，流量为 \(\inf\) 的边即可。

这样我们就只添加了 \(O(n)\) 条边，将原问题转化为了最大流问题，可以使用 \(\text{Dinic}\) 算法在 \(O(n \sqrt n)\) 的时间复杂度内求解。

\(\text{UVG}\) 游戏

在无向图上有一枚棋子放在起点上，两人轮流操作将棋子移动到相邻且没有去过的点，无法行动则失败。

结论：若任意最大匹配方案的点集都包含起点，则先手必胜，否则先手必败。

把访问过的点看作被删除。

按照博弈论的流程，分两步来证明该结论。

• 任意的必胜态都能到达必败态。

考虑原图的一个最大匹配边集 \(M\)，因为 \(u\) 是必胜点，所以一定存在 \((u,v) \in M\)。

删去点 \(u\) 之后，新图的最大匹配数会减小 \(1\)，且 \(M \setminus \{(u,v)\}\) 是其中一种最大匹配方案，那么可知 \(v\) 在新图中是必败点。

• 任意的必败态都只能到达必胜态。

因为 \(u\) 不被所有最大匹配方案所包含，所以删去 \(u\) 之后的新图的最大匹配数不变，令这个值为 \(p\)。

对于任意与 \(u\) 相邻的点 \(v\)，若 \(v\) 是必败点，则有一种新图的匹配方案 \(M\)，满足 \(|M|=p\)，且不存在 \(w\) 使得 \((v,w) \in M\)。

那么可以在原图中构造出一个匹配方案为 \(M \cup \{(u,v)\}\)，其大小为 \(p+1\)，与原图的最大匹配数为 \(p\) 相悖。

故 \(v\) 一定是必胜点，证完了喵喵喵。

必胜策略

若当前点是必胜点，走一条在任意匹配方案中是匹配边的边即可。

拓展性质

对于任意二分图，设其最大匹配为 \(p\)，则图上至少有 \(p\) 个必胜点，且任意一个最小点覆盖集内的点都是必胜点。

对于任意一个最小点覆盖集 \(S\)，集合内的 \(p\) 个点可以覆盖所有边，设存在 \(u \in S\)，且 \(u\) 不是必胜点，那么就会存在 \(M=(V,E)\) 是一个最大匹配，满足 \(u \notin V\)。

那么已知 \(S\) 内的点可以覆盖所有边，也就可以覆盖 \(E\) 中的所有边，由于 \(u \notin V\)，即 \(S \setminus \{u\}\) 可以覆盖 \(E\) 中的所有边。

因为 \(E\) 中的边两两没有公共端点，所以一个点最多覆盖一条 \(E\) 中的边，但 \(|S \setminus \{u\}| = p-1 < p = |E|\)，故 \(|S \setminus \{u\}|\) 不可能覆盖 \(E\) 中的所有边，与上文矛盾。

故 \(S\) 中的点都是必胜点，得证。

\(\text{Dilworth}\) 定理与 \(\text{Mirsky}\) 定理

偏序集中的概念：

• 链：若一个点集 \(S\)，满足 \(\forall x,y \in S,x \not= y\)，\(x\) 和 \(y\) 都有偏序关系，则称 \(S\) 是链，注意和传统图论中链的概念进行区分，偏序集中的链是一个集合，在 \(\text{DAG}\) 上不要求连续。

• 反链：若一个点集 \(S\)，满足 \(\forall x,y \in S,x \not= y\)，\(x\) 和 \(y\) 都没有偏序关系，则称 \(S\) 是反链。

• 链覆盖：用若干条不交的链覆盖偏序集中所有点，等价于 \(\text{DAG}\) 中的可重路径覆盖。

• 反链覆盖：用若干条不交的反链覆盖偏序集中所有点。

\(\text{Dilworth}\) 定理：偏序集的最大反链长度 \(=\) 最小链覆盖。

令最大反链长度为 \(p\)，最小链覆盖为 \(q\)，考虑分两步证明。

• \(q \geq p\)

由于最大反链中的点两两没有偏序关系，一条链显然最多只能覆盖其中的一个点。

那么就至少需要 \(p\) 条链才能覆盖掉最大反链中的所有点，故 \(q \geq p\)。

• \(p \geq q\)

考虑构造一个恰好 \(q\) 个点的反链来证明该命题。

先对于原图跑传递闭包，并建出对应的二分图，把所有问题都转化到二分图上考虑。

首先有引理，在该二分图的任意一组最小点覆盖 \(S\) 中，不可能存在点 \(u\)，使得 \(u_1,u_2 \in S\)。

采用反证法证明，设存在这样的一个点 \(u\)，那么 \(u_1\) 和 \(u_2\) 一定都不是孤立点，设与 \(u_1\) 有边相连的点集为 \(Q\)，与 \(u_2\) 有边相连的点集为 \(P\)，如下图：

由于是跑过传递闭包的二分图，所以 \(P\) 中的每一个点到 \(Q\) 中的每一个点都有边。

接下来说明：\(P\) 和 \(Q\) 一定至少有一个集合是 \(S\) 的子集。

若 \(\exists x \in P,x \notin S\)，因为 \(x\) 到 \(Q\) 中所有点都有边，那么 \(Q\) 必须是 \(S\) 的子集，反之亦然。

进一步地，若 \(P\) 是 \(S\) 的子集，易得 \(u_2\) 的所有边都被覆盖，则 \(S \setminus \{u_2\}\) 是该二分图的一组点覆盖；

若 \(Q\) 是 \(S\) 的子集，易得 \(u_1\) 的所有边都被覆盖，则 \(S \setminus \{u_1\}\) 是该二分图的一组点覆盖。

这与 \(S\) 是最小点覆盖产生矛盾，故这样的点 \(u\) 不存在！

接下来构造集合 \(T=\{u|u_1,u_2 \notin S\}\)，设二分图最大匹配为 \(m\)，根据上述引理易得 \(|T|=n-m=q\)。

对于任意 \(x,y \in T\)，因为 \(x_1,x_2,y_1,y_2\) 均不在最小点覆盖中，所以 \(x\) 和 \(y\) 之间一定没有边，否则点覆盖就不合法。

综上，\(T\) 是一个合法的，大小恰好为 \(q\) 的反链，证完了 \(\sim\)

\(\text{Mirsky}\) 定理即为 \(\text{Dilworth}\) 定理的对偶形式：偏序集的最长链 \(=\) 最小反链覆盖，证明过程类似。

\[\text{Thanks for your reading.} \]