省选-二分图

· · 个人记录

二分图

对于一张图 G = (V, E)（无孤立点，否则边覆盖可能不存在），有：

还有：

利用定义解题

二分图的性质：没有奇环。

还可以用模板的匹配解决一些基础一点的问题。

时间复杂度（匈牙利算法）：O(VE)。

CF1537F Figure Fixing

::::info[这道题是二分图定义性质题] CF1537F Figure Fixing。

首先，我们特判掉奇偶性不同的。

然后，这道题中，我们需要先考虑哪些情况是可以随便填的。

然后我们发现奇环上的点可以任意加一个偶数的东西，就相当于在这个点加上 2，旁边的一人加一个 1。

但是这个结论不足以做这道题，我们需要扩展。我们看与奇环联通的点，随便加 2 贡献都可以转移到环上。

所以奇环是可以的。

然后其它情况就是二分图了，二分图只需要看左右的差量是否正确就行了。

::::

CF1684G Euclid Guess

::::info[这个题是性质题+构造]

CF1684G Euclid Guess。

不要看错题了，数对构成的序列 p，而不是序列两两进行。

首先，我们发现 m 的限制很不好。

然后我们发现，大的元素一定会占用一个小的，对应上面就是 b \mod a。

然后小的元素可以被大的使用，也可以自我消耗，所以我们需要尽可能少用小的元素。

我们直接让 a|b，于是记录 b，然后进行 (a+b,b)，接着记录 a，然后进行 (a,b)，此时如果 a|b 就结束了。

因为无论如何，我们都需要用到 b 的因数（这是辗转相除，很妙）。

所以最后，我们对于每一个大元素 b 需要匹配小元素，直接二分图匹配，a|b 且 a+b*2\le m 的有边。

所以题目里要求最后构造出来的总对数 \le2*10^4 这个条件其实没用。

::::

P2764 最小路径覆盖问题

::::info[这个题是二分图建模，然后利用拆点的性质]

给定一个 DAG，用最少的不交路径覆盖所有的点。

这道题是不交路径，所以我们可以设置每一个点只有一条出边和入边，这个限制可以用我们学过的拆点来限制。

然后二分图最大匹配就行了（网络流写过了）。

现在有一个升级版，就是用最小的可重复路径覆盖所有的点。我们可以找到最小路径覆盖，然后可重的就是可以绕过去。

::::

CF1728F Fishermen

这是一个性质题，需要简化题目的问题，然后结合二分图可以找到左边字典序或者和最小的匹配方式。

::::info[思路]

CF1728F Fishermen。

看完题后，我们需要先想想这道题的性质。

本题限制很多，尝试简化。

首先求的是最小的，那么 b 中间也一定是最小的了，所以这个限制可以先不用管。

还有限制：b_i>b_{i-1} 这个限制可以通过排序直接去除掉，只需要保证 b 不相同就行了。

这样，一个数只能匹配一个 a，做二分图匹配就行了。

随便结合一下性质：二分图匹配可以找到最小的解。

注意匈牙利算法清空 vis 需要在匹配成功后。

::::

CF1620F Bipartite Array

CF1620F Bipartite Array。

::::info[这是一个性质题，需要观察出这道题的二分的性质] CF1620F Bipartite Array。

看完题肯定能发现性质：如果有长度大于等于 3 的逆序对，就不是二分的，因为这样会出现奇环。

所以我们发现，这道题中我们需要让 a 排成两个上升子序列，可以不连续。

所以可以直接 dp，a 表示当第 i-1 位取正时，另一段末尾的最小可能值，b 表示当第 i-1 位取负时，另一段末尾的最小可能值。

P1963 [NOI2009] 变换序列

P1963 [NOI2009] 变换序列。

::::info[字典序最小处理技巧，从后往前] 如果没有字典序的限制，这可能就是绿。一个数位置最多有两个数可以放。

然后我们发现这个不能行的原因是，后面会去替换前面的最大的边，所以我们只需要先处理后面的，再处理前面的。

::::

图博弈

棋子每一步走一条边，且不能走到已经走过的点，不能移动就输了，谁会赢？ >结论：如果途中存在一个最大匹配不含 $x$，则 $A$ 必败，否则 $A$ 必胜。（这个结论并不仅限于二分图。） ### 结论证明 先证明包含 $A$ 就必胜。如果所有的最大匹配都包含 $x$，$A$ 第一步会走到一个 $x$ 的匹配点，然后接下来 $B$ 只能走一个非匹配边，$A$ 接着又会有匹配边，循环往复。最后一定是 $B$ 走不动了，因为最后如果是非匹配边，一定有一种匹配是选择了这条边，因为这并不影响其他地方。 然后还需要向明不包含 $A$ 必败。如果 $x$ 不在最大匹配中，所以 $x$ 所有的邻居都是匹配点，结合上面的，$B$ 必胜，即 $A$ 必败。 ### 模板题：P4055 [JSOI2009] 游戏 ::::info[模板题] [P4055 [JSOI2009] 游戏](https://www.luogu.com.cn/problem/P4055)。 这个就是模板了，找到所有最大匹配都含有的点的方法就是对于每一个可以为 $0$ 的点，连着一个匹配点，就可以把这个点匹配的点踢掉，成为非匹配点。 :::: ## Konig 定理 ### 定理内容 在二分图中： $$最大匹配 = 最小点覆盖$$ --- ### 证明 证明思路：找到显然的 $\ge$ 或 $\le$，然后证明 $=$ 成立。 ::::info[证明] 我们发现 $最小点覆盖 \ge 最大匹配$，所以我们只需要构造一组大小等于最大匹配的最小点覆盖。 首先，用匈牙利算法求出图的一个最大匹配。然后，从左部的每一个未匹配点出发，走一遍“匈牙利算法”中的交错路（依次经过非匹配边、匹配边、非匹配边……），并标记所有访问到的点。 若左端点未标记，则它是匹配点（不然一开始就会被标记）。 若右端点标记，那它一定是匹配点。 然后对于点集：左部所有未被标记的点 + 右部所有被标记的点，这是一个大小 $\le$ 最大匹配的点集。 为什么？对于每一条边，如果左边的点被标记了，但是右边没有，那么这是匹配边，又因为如果这是匹配边，唯一到达左边的方法就是通过这条边，所以矛盾了。 所以每一条边左右都被标记了。 所以这也是一个点覆盖。 然后就得出了结论，在二分图中： $$最大匹配 = 最小点覆盖$$ :::: ### 常见结论 #### 关于点匹配边 $$ \text{最小点覆盖} + \text{最大独立集} = |V| $$ 这个还是用 $\le$ 和 $\ge$ 证明。 ::::info[证明] 最小点覆盖的补集是独立集，这个集合大小 $\le$ 最大独立集。 最大独立集的补集是点覆盖，这个集合大小 $\ge$ 最小点覆盖。 所以他们的和又 $\le |V|$ 又 $\ge |V|$，所以相等。 :::: --- #### 关于边匹配点 若图不含孤立点，则 $$ \text{最小边覆盖} + \text{最大匹配} = |V| $$ 同理证明方法： ::::info[和上面同样的证明方法] 最小边覆盖的补集是匹配，这个集合大小 $\le$ 最大独立集。 最大匹配的补集是边覆盖，这个集合大小 $\ge$ 最小点覆盖。 所以他们的和又 $\le |V|$ 又 $\ge |V|$，所以相等。 :::: ::::info[另一种证明方法（貌似更简单）]{open} 证明思路：先取一个最大匹配 $M$，它覆盖了 $2|M|$ 个顶点。为了覆盖剩下的 $|V| - 2|M|$ 个顶点，至少需要添加 $|V| - 2|M|$ 条边（每条边覆盖一个新顶点），因此最小边覆盖大小为 $|M| + (|V| - 2|M|) = |V| - |M|$。 :::: ---- ::::info[关于网络流] **Konig 定理**：在二分图中，最大匹配的大小等于最小点覆盖的大小。 因为最小点覆盖大于等于最大匹配。 然后构造大小为最大匹配的点覆盖： 跑完最大流后，令 $V'$ 为残余网络上左部中源点能到达的点与右部中源点不能到达的点。则 $V'$ 是点覆盖：若一条边左端不在 $V'$ 中（即左端不可达），则右端必在 $V'$ 中（因为若右端可达，则左端可通过该边到达，矛盾）；同理，若右端不在 $V'$ 中，则左端必在 $V'$ 中。故所有边被覆盖。而 $|V'|$ 等于最小割容量，即最大流值，也就是最大匹配数。 因此最大匹配 = 最小点覆盖。 1. **最小边覆盖与最大匹配**：若图不含孤立点，则 $$ \text{最小边覆盖的大小} + \text{最大匹配的大小} = |V|. $$ 证明思路：先取一个最大匹配 $M$，它覆盖了 $2|M|$ 个顶点。为了覆盖剩下的 $|V| - 2|M|$ 个顶点，至少需要添加 $|V| - 2|M|$ 条边（每条边覆盖一个新顶点），因此最小边覆盖大小为 $|M| + (|V| - 2|M|) = |V| - |M|$。 2. **最小点覆盖与最大独立集**： $$ \text{最小点覆盖的大小} + \text{最大独立集的大小} = |V|. $$ 证明思路：独立集 $V'$ 的补集 $V \setminus V'$ 是点覆盖，反之亦然，两者构成一一对应。因此最大独立集对应最小点覆盖，且大小之和为 $|V|$。 这两个关系说明，对于任意图，如果我们能求出最大匹配，就能得到最小边覆盖；如果能求出最小点覆盖，就能得到最大独立集。而在二分图中，由于有 K?nig 定理（最大匹配 = 最小点覆盖），我们可以通过最大匹配同时求出最小点覆盖和最大独立集，进而也得到最小边覆盖。这为后续网络流求解二分图相关问题奠定了基础。 :::: ## Dilworth 定理 $$DAG 最长反链 = 最小可重链覆盖$$ 最长反链：最大的子集使得互相不可达。注意，这是集合！ 最小可重链覆盖是指用最少的几条可重路径把图中所有顶点都覆盖至少一次。 ### 证明 取走一个没有入度的点。 最长反链不变。则直接把这个点接回去。 最长反链也减了 1，则把这个点作为一个单独的链加入。 反正感性理解一下。 ### P4298 [CTSC2008] 祭祀 [P4298 [CTSC2008] 祭祀](https://www.luogu.com.cn/problem/P4298)。 ::::info[这道题就是让我们求最长反链] #### Question 1 问个数就相当于问反链大小，根据 Dilworth 定理，最长反链 = 最小可重链覆盖。 所以我们只需要求最小可重链覆盖，怎么求？可重的好像不好求，我们先考虑怎么把问题转化为不可重链覆盖。 >题解里说：Dilworth 定理原本的描述是对于偏序集来说的。你可以将偏序集理解为“求过传递闭包的 DAG”，于是“可重”或“不可重”就无所谓了。 也就是我们将问题转化成传递闭包，先处理一下再进行覆盖。相当于我们可以选择跳过一写点，这样处理之后，“可重”或“不可重”就无所谓了。 传递闭包可以用 Floyd 求。 然后既然是求不可重的，每一个点最多 $1$ 条出点或出边，拆点，进行二分图匹配就行了。 #### Question 3 问题 $2$ 需要问题 $3$ 做铺垫？ 对于普通的一条链，我们需要随便选一个点，且这是最优的。 对于两条链汇集的交点一定不是最优的，因为我们最好在分叉上选。 所以我们对于每一个点，假设选它。 #### Question 2 我们发现对于上面的链的情况，有一堆节点只能选一个，我们对相同排除就行了。 --- Floyd 枚举顺序别写反了。 :::: --- ### CF1404E Bricks ---- ## 二分图完美匹配与 Hall 定理 **Hall 定理** 对于二分图 $ G = (X, Y, E) $，存在一个完美匹配当且仅当 $$ \forall S \subseteq X,\quad |N(S)| \ge |S|, $$ 其中 $ N(S) $ 表示 $ S $ 在 $ Y $ 中的邻点集合。 --- 使用归纳法证明，有点意思。 ::::info[证明] 假设二分图满足 Hall 条件。 如果不存在完美匹配，就取一个最大的匹配，它肯定没覆盖某个左边的点。 从这个点出发，交替走“非匹配边从左边到右边、匹配边从右边到左边”，把能走到的所有点找出来。 在这个可达集合里，左边的点（除了起点）和右边的点是一一配对的（因为匹配边），所以左边的点比右边的点多一个。 但所有左边点的邻居都只在这些右边点里，这就违背了 Hall 条件——邻居数反而比左边点数少。因此，Hall 条件成立时，完美匹配必然存在。 --- 假设二分图不满足 Hall 条件。 即存在某个左边的子集 $S$，它的邻居数 $|N(S)| < |S|$。那么 $S$ 中的点要匹配到不同的右边点，但邻居数不够，因此无法形成完美匹配。 :::: ::::info[网络流证明] **证明概要** - **必要性**：若存在饱和 $ X $ 的匹配，则 $ S $ 中每个顶点在匹配中有一个不同的邻点，这些邻点都在 $ N(S) $ 中，故 $ |N(S)| \ge |S| $。 - **充分性**（利用最大流最小割定理）：构造网络流：源点 $ s $ 连每个 $ x \in X $（容量 1），每个 $ y \in Y $ 连汇点 $ t $（容量 1），原边 $ x \to y $ 容量 1。则最大匹配值等于最大流值。 对任意 $ s-t $ 割，设 $ S $ 为割中未被割掉 $ s \to x $ 边的 $ X $ 中点集，则 $ N(S) $ 必须全部割掉与 $ t $ 的边，否则存在增广路。割的容量至少为 $ |X| - |S| + |N(S)| $。由 Hall 条件 $ |N(S)| \ge |S| $ 得该值 $\ge |X|$，故最小割 $\ge |X|$。由最大流最小割定理，最大流 $\ge |X|$，即存在饱和 $ X $ 的匹配。 :::: ### AT_arc106_e [ARC106E] Medals [AT_arc106_e [ARC106E] Medals](https://www.luogu.com.cn/problem/AT_arc106_e)。 首先是二分图建模，这道题相当于是天匹配人，把每个人拆成 $k$ 个，进行完美匹配，我们需要找到完美匹配。 由于是可行性，所以我们想到了 Hall 定理。 我们二分答案判断是否可行，判断的时候用 Hall 定理。 具体写法中 $f_i$ 表示出勤员工集合是 $i$ 的子集的天数，然后 `mid-f[m-i]` 表示连的边。