CF1537F Figure Fixing。

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

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

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

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

所以奇环是可以的。

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

CF1684G Euclid Guess。

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

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

• $x\le \frac{m}{3}$ 一定可以构造出来 $(3x,2x)$。

• $x\ge \frac{m}{2}$，我们无法构造。

• $\frac{m}{3}\le x\le \frac{m}{2}$，构造 $a\le \frac{m}{3}$，$b\ge \frac{m}{3}$，需要满足 $a+b*2\le m$，就是 $(a+b,a+b*2)$（$(a,a+b)$ 不行，因为会成为 $b \mod a$）。（后面成为大元素）

然后我们发现，大的元素一定会占用一个小的，对应上面就是 $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$ 这个条件其实没用。

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

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

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

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

CF1728F Fishermen。

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

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

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

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

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

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

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

CF1620F Bipartite Array。

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

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

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

如果没有字典序的限制，这可能就是绿。一个数位置最多有两个数可以放。

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

P4055 [JSOI2009] 游戏。

这个就是模板了，找到所有最大匹配都含有的点的方法就是对于每一个可以为 $0$ 的点，连着一个匹配点，就可以把这个点匹配的点踢掉，成为非匹配点。

我们发现 $最小点覆盖 \ge 最大匹配$，所以我们只需要构造一组大小等于最大匹配的最小点覆盖。

首先，用匈牙利算法求出图的一个最大匹配。然后，从左部的每一个未匹配点出发，走一遍“匈牙利算法”中的交错路（依次经过非匹配边、匹配边、非匹配边……），并标记所有访问到的点。

若左端点未标记，则它是匹配点（不然一开始就会被标记）。

若右端点标记，那它一定是匹配点。

然后对于点集：左部所有未被标记的点 + 右部所有被标记的点，这是一个大小 $\le$ 最大匹配的点集。

为什么？对于每一条边，如果左边的点被标记了，但是右边没有，那么这是匹配边，又因为如果这是匹配边，唯一到达左边的方法就是通过这条边，所以矛盾了。
所以每一条边左右都被标记了。

所以这也是一个点覆盖。

然后就得出了结论，在二分图中：

$最大匹配 = 最小点覆盖$

最小点覆盖的补集是独立集，这个集合大小 $\le$ 最大独立集。

最大独立集的补集是点覆盖，这个集合大小 $\ge$ 最小点覆盖。

所以他们的和又 $\le |V|$ 又 $\ge |V|$，所以相等。

最小边覆盖的补集是匹配，这个集合大小 $\le$ 最大独立集。

最大匹配的补集是边覆盖，这个集合大小 $\ge$ 最小点覆盖。

所以他们的和又 $\le |V|$ 又 $\ge |V|$，所以相等。

证明思路：先取一个最大匹配 $M$，它覆盖了 $2|M|$ 个顶点。为了覆盖剩下的 $|V| - 2|M|$ 个顶点，至少需要添加 $|V| - 2|M|$ 条边（每条边覆盖一个新顶点），因此最小边覆盖大小为 $|M| + (|V| - 2|M|) = |V| - |M|$。

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 定理（最大匹配 = 最小点覆盖），我们可以通过最大匹配同时求出最小点覆盖和最大独立集，进而也得到最小边覆盖。这为后续网络流求解二分图相关问题奠定了基础。

Question 1

问个数就相当于问反链大小，根据 Dilworth 定理，最长反链 = 最小可重链覆盖。

所以我们只需要求最小可重链覆盖，怎么求？可重的好像不好求，我们先考虑怎么把问题转化为不可重链覆盖。

题解里说：Dilworth 定理原本的描述是对于偏序集来说的。你可以将偏序集理解为“求过传递闭包的 DAG”，于是“可重”或“不可重”就无所谓了。

也就是我们将问题转化成传递闭包，先处理一下再进行覆盖。相当于我们可以选择跳过一写点，这样处理之后，“可重”或“不可重”就无所谓了。

传递闭包可以用 Floyd 求。

然后既然是求不可重的，每一个点最多 $1$ 条出点或出边，拆点，进行二分图匹配就行了。

Question 3

问题 $2$ 需要问题 $3$ 做铺垫？

对于普通的一条链，我们需要随便选一个点，且这是最优的。

对于两条链汇集的交点一定不是最优的，因为我们最好在分叉上选。

所以我们对于每一个点，假设选它。

Question 2

我们发现对于上面的链的情况，有一堆节点只能选一个，我们对相同排除就行了。

Floyd 枚举顺序别写反了。

假设二分图满足 Hall 条件。

如果不存在完美匹配，就取一个最大的匹配，它肯定没覆盖某个左边的点。

从这个点出发，交替走“非匹配边从左边到右边、匹配边从右边到左边”，把能走到的所有点找出来。

在这个可达集合里，左边的点（除了起点）和右边的点是一一配对的（因为匹配边），所以左边的点比右边的点多一个。

但所有左边点的邻居都只在这些右边点里，这就违背了 Hall 条件——邻居数反而比左边点数少。因此，Hall 条件成立时，完美匹配必然存在。

假设二分图不满足 Hall 条件。

即存在某个左边的子集 $S$，它的邻居数 $|N(S)| < |S|$。那么 $S$ 中的点要匹配到不同的右边点，但邻居数不够，因此无法形成完美匹配。

证明概要

• 必要性：若存在饱和 $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$ 的匹配。