图论 3
Published:
三元环
无向图三元环
这个做法感觉非常不自然，感觉很难从零想到。所以这里也就记录一下这个做法，及其中涉及到的结论。
我们把无向图定向成一个 DAG：对于一条边 $u \leftrightarrow v$，把度数小的点往度数大的连，如果度数一样则把编号小的往编号大的连。
接下来有一个核心结论：在这张 DAG 上，每个点的出度是 $O(\sqrt m)$ 的。
证明：对于 $u$ 的每个后继 $v$，$deg_v \ge deg_u$，而 $v$ 总共有 $deg_u$ 个。因此与 $u$ 相关的度数是 $\sum deg_v \ge deg_u^2$。而一张图的总 $deg$ 是 $\Theta(m)$ 的，因此 $deg_u \in O(\sqrt m)$。
一个推论就是三元链 $u \to v \to w$ 只有 $O(m \sqrt m)$ 个。因为对于每条边 $u \to v$，$v \to w$ 只有 $O(\sqrt m)$ 个。
注意到原图的每个三元环在新图上必定是 $u \to v \to w$ 加上一个 $u \to w$。我们只要枚举所有的 $u \to v \to w$，看看有没有 $u \to w$ 这条边就行了。时间复杂度 $O(m \sqrt m)$。
因此我们又有一个推论：无向图三元环的个数是 $O(m \sqrt m)$。在 $m$ 不是特别大的时候，我们可以找出所有三元环，并进行一些统计。
有向图三元环
有向图三元环的形成条件比无向图更加苛刻，所以数量更少。
把有向图看成无向图，找出所有无向图上的三元环，依次检验在原来的有向图上是否是合法的三元环即可。时间复杂度 $O(m \sqrt m)$。
无向图四元环
首先像三元环一样建图。在新图上四元环有以下三种形态：
- $a \to b \to c$，$a \to d \to c$
- $a \to b \to c$，$a \to d \gets c$
- $a \to b \gets c$，$a \to d \gets c$
具体怎么统计？别忘了刚才的结论：新图的三元链只有 $O(m \sqrt m)$ 个。
对于第一种情况，对于所有三元链整理出首尾相同的。比如说以 $u$ 开头 $w$ 结尾的三元链有 $C$ 个，就能造成 $\binom C 2$ 的贡献。
对于第二种情况，我们首先找三元链 $a \to b \to c$。剩下的 $a \to d \gets c$ 其实也是“三元链”，但是需要新图的反图来快速查找 $d$ 的入边。
对于第三种情况，我们找两条类似于第二种情况的类似三元链 $a \to b \gets c$ 和 $a \to d \gets c$，然后依然用 $\binom C 2$ 来统计即可。
所有东西的时间复杂度都基于三元链的个数 $O(m \sqrt m)$，因此时间复杂度 $O(m \sqrt m)$。
稠密图上的快速算法
- 无向图：[ABC258G] Triangle
- 有向图：Codeforces Gym 100342J Triatrip
注意到三元环的个数 $O(m \sqrt m)$ 此时变成了 $O(n^3)$，这很坏了。考虑换个思路。
最直接的暴力就是枚举三元组 $(u,v,w)$，看看是否有 $u \to v$、$v \to w$、$w \to u$ 三条边。这里有一个地方可以优化：我们先枚举 $u,v$，用 bitset 的 count 函数找到满足 $v \to w$ 和 $w \to u$ 的 $w$ 的数量。
时间复杂度 $O(\frac {n^3} w)$。
Hall 定理
二分图 $G$ 的左部为 $X$，右部为 $Y$，且 $\lvert X \rvert \le \lvert Y \rvert$。
对于 $S \subseteq X$，$N(S)$ 表示 $S$ 能够通过一条边走到的右部点集合。
以下若遇到多重匹配问题，$a_i$ 表示左部点的第 $i$ 个的匹配上限，$b_i$ 表示右侧的。
二分图完美匹配的充要条件
这是经典的 Hall 定理。
二分图 $G$ 有完美匹配的充要条件为：
\[\forall S \subseteq X, \lvert S \rvert \le \lvert N(S) \rvert\]证明
必要性显然，证充分性。考虑归纳。
若 $\forall S, \lvert S \rvert < \lvert N(S) \rvert$ 不取等，则我们可以选择一条任意边 $(u,v)$，删掉 $u,v$ 两个点和相关边，此时剩下的二分图满足 Hall 定理的使用条件 $\forall S, \lvert S \rvert \le \lvert N(S) \rvert$，化为子问题。
否则，$\exists S, \lvert S \rvert = \lvert N(S) \rvert$。$S$ 与 $N(S)$ 形成完美匹配，我们把这些点和相关边删掉。此时剩下的图如果满足 Hall 定理使用条件则化为子问题，否则可以找到一个 $T$ 使得 $\lvert T \rvert < \lvert N(T) \rvert$。
接下来证明这种情况不可能出现，即剩下的图必定满足 Hall 定理使用条件，采取反证法。观察点集 $S \sqcup T$，$\lvert N(S \sqcup T) \rvert \le \lvert N(S) \cup N(T) \rvert \le \lvert N(S) \rvert + \lvert N(T) \rvert < \lvert S \rvert + \lvert T \rvert = \lvert S \sqcup T \rvert$。总之 $\lvert N(S \sqcup T) \rvert < \lvert S \sqcup T \rvert$。但是原图是满足 Hall 定理使用条件的，必有 $\lvert N(S \sqcup T) \rvert \ge \lvert S \sqcup T \rvert$，因此矛盾。
二分图最大匹配的显式表达式
经典 Hall 定理的加强版。
二分图 $G$ 的最大匹配等于：
\[\lvert X \rvert - \max\limits_{S \subseteq X} (\lvert S \rvert - \lvert N(S) \rvert)\]证明
首先把式子化成 $\min$：
\[\min\limits_{S \subseteq X} (\lvert X \rvert - \lvert S \rvert + \lvert N(S) \rvert)\]我们放回那个二分图的网络流图上。可以看成，在左部选一个集合 $S$ 不割，割掉 $S$ 的补集和 $N(S)$，这样整张图不连通。取一个 $\min$ 就是最小割，根据最大流最小割定理，这个值等于最大流，即二分图最大匹配。
二分图多重完美匹配的充要条件
\[\forall S \subseteq X, \sum\limits_{i \in S} a_i \le \sum\limits_{i \in N(S)} b_i\]证明
把左部点 $i$ 拆成 $a_i$ 个点，右部点 $i$ 拆成 $b_i$ 个点，直接使用 Hall 定理。排除掉一些显然劣的情况就得到了要证的命题。
二分图多重最大匹配的显式表达式
\[\left( \sum\limits_{i \in X} a_i \right) - \max\limits_{S \subseteq X} \left( \left( \sum\limits_{i \in S} a_i \right) - \left( \sum\limits_{i \in N(S)} b_i \right) \right)\]证明同上。
正则二分图的完美匹配
$k$ 正则二分图：每个点度数均为 $k$ 的二分图。显然正则二分图左右两部点数相同。
任意正则二分图有完美匹配。
证明：反证法。
假设 $\exists S, \lvert S \rvert < \lvert N(S) \rvert$，则 $k \lvert N(S) \rvert = \sum\limits_{u \in N(S)} deg_u \ge \sum\limits_{u \in S} deg_u = k \lvert S \rvert > k \lvert N(S) \rvert$，导出矛盾。
具体方案：$k$ 为 $2$ 的幂
当 $k$ 是 $2$ 的幂时，我们有一个 $O(nk) = O(m)$ 的线性算法。
找一条 Euler 回路，相当于给每条边定向。此时每个点出度入度均为 $\frac k 2$。我们删掉一个方向的边然后忽略定向，就变为 $\frac k 2$ 的子问题。递归到 $k=1$ 解决。
其余情况的 $k$ 有随机算法。
广义 Hall 定理
$S_X \subseteq X$，$S_Y \subset Y$。存在一个匹配 $M_{XY}$ 同时包含 $S_X$ 和 $S_Y$ 的充要条件是存在匹配 $M_X$ 包含 $S_X$，存在匹配 $M_Y$ 包含 $S_Y$。
证明
考虑直接把 $M_X$ 和 $M_Y$ 叠在一起，重边重复计算。$M_X$ 和 $M_Y$ 每个点度数为 $1$，因此叠出来的图度数最多为 $2$。因此必定是若干个环和链的并。环一定是偶环，间隔取。链如果是奇链，也可以间隔取。如果是偶链，则必有一个端点实际上不在 $X$ 或者 $Y$ 中，忽略即可。这样就构造出了一组合理的 $M_{XY}$。
Hall 定理 例题
CF1373F Network Coverage
TODO:
P3679 [CERC2016] 二分毯 Bipartite Blanket
给定一个二分图，点有点权。给定一个数 $t$，求有几个点集权值和 $\ge t$ 且被至少一个匹配覆盖。
$1 \le n,m \le 20$。
显然是广义 Hall 定理。分别统计两边（高位前缀和），双指针最终统计。
[AGC037D] Sorting a Grid
TODO:
P9528 [JOISC 2022] 蚂蚁与方糖
TODO:
[AGC029F] Construction of a tree
给定 $[1,n]$ 的 $n-1$ 个子集 $E_{1,\cdots,n-1}$。
问能否从每个子集中选出选出两个元素 $u_i,v_i \in E_i$，使得把所有 $u_i \leftrightarrow v_i$ 连起来形成一棵树。输出一组任意方案或报告无解。
$n \le 10^5$，$\sum\limits_{i=1}^{n-1} \lvert E_i \rvert \le 2 \times 10^5$。
我们令 $1$ 为根。建一个二分图，左部是 $[2,n]$ 的所有点，右部是 $E$ 的这些集合。对于所有点 $u$，若 $u \in E_i$ 则连边 $u \to E_i$。发现有解的一个必要条件是这张二分图存在完美匹配。
Dinic 跑一遍之后得到了一个任意的完美匹配。不难构造：以 $1$ 为根开始，把完美匹配中能连到 $1$ 就连到 $1$，然后对这些点继续递归。如果递归到所有点则 OK，否则无解。
时间复杂度 $O(\sqrt n m)$。
斯坦纳树
NP-Hard 问题
TODO:
需要一个 $O(3^k n + 2^k m \log m)$ 的做法。
状压 DP
TODO:
P3264 [JLOI2015] 管道连接
TODO: