Hall 定理学习笔记

定义

对于一张二分图 $G = (V, E)$ ，设其左右部点集分别为 $V_L,V_R$ ，不妨认为 $(|V_L|\leq |V_R|)$ ，定义该二分图的一组 完备匹配 为左部 $V_L|$ 个点全部成为匹配点的匹配。

Hall 定理讲的是，定义 $N (v)$ 为节点 $v$ 的邻居集，如果对于任意 $S\subseteq V_L$ ，均有 $|S|\leq|\bigcup\limits_{u\in S} N(u)|$ ，则该二分图存在一组完备匹配。

证明参考资料

一些推论

对于一张 $k$ 正则二分图（每个点度数都为 $k$ ，且 $k\geq1$ ），若 $V_L|=|V_R|$ ，则必有 $k$ 组边不交的完美匹配。

证明：考虑归纳，只需证明该二分图存在一组完美匹配，那么删去这些匹配边后会得到 $k - 1$ 正则二分图，归纳即证。
考虑 hall 定理，若存在 $S\subseteq V_L$ 使得 $|S|>|\bigcup\limits_{u\in S} N(u)|$ ，由于 $|\bigcup\limits_{u\in S} N(u)|$ 中的点的度数之和必定 $\geq$ $k ∣ S ∣$ ，但该点集的点数却小于 $∣ S ∣$ ，显然矛盾，因此 hall 条件成立，存在完美匹配。
左右两部分别为 $V_L,V_R$ 的二分图最大匹配为 $|V_L|-\max\limits_{S\subseteq V_L}(|S|-|\bigcup\limits_{u\in S} N(u)|)$ 。
很好理解。

应用

题目类型很多。

直接应用

数据范围比较小，可以 $2^{n}$ 枚举集合 check 是否满足 hall 条件

AT_arc106_e [ARC106E] Medals

枚举集合完之后问题转化成了：求多少天才能让并集大小为 $K$ 。

试试二分，好像更好做了，但推式子还是推不出来答案。

然后观察一下发现答案是 $2 nk$ 级别的，是可以直接扫一遍的。

剩下就很简单了。

数据结构维护 hall 条件

正常来说想使用 hall 来求/判断最大匹配需要枚举所有集合 $S$ ，复杂度不可接受

但在某些题目中合法（或者说有用）的 $S$ 可能会满足某种性质（比如是一段区间），从而使得枚举量大大减少，可以用数据结构直接维护。

P3488 [POI 2009] LYZ-Ice Skates

直接应用，显然有用的人的集合一定是一段区间，推推式子就转化成了最大子段和。

CF338E Optimize!

有用集合是值域上一段前缀。

AT_arc076_d [ARC076F] Exhausted?

以人为左部点列 hall 条件，求它们的并；可以看成先选出一段并区间，再选出尽可能多的人，这样方便用数据结构维护。

求并可以转化成求补集交，扫描线补集右端点，维护所有左端点答案。

P9528 [JOISC 2022] 蚂蚁与方糖

如果不单单是判断，而是求最大匹配会有什么变化呢？

发现区别在于：现在可能选出多段连续区间。

形式化的描述一下简化后的问题：设蚂蚁前缀和为 $S_i$ ，方糖前缀和为 $T_i$ ，你要选出若干段区间 ${l_1,r_1,...l_k,r_k\}$ ，最大化 $\sum\limits_{i=1}^k T_{r_i-L}-T_{l_i+L-1}-(S_{r_i}-S_{l_i-1})$ 最大。

化一下式子： $\sum\limits_{i=1}^k (T_{r_i-L}-S_{r_i})+(S_{l_i-1}-T_{l_i+L-1})$

令 $P_i=T_{i-L}-S_i$ ， $Q_i=S_i-T_{i+L}$ ，那么就是每个点有权值 $P, Q$ ，要选出形如 $QPQP ... QP$ 的若干个点，最大化选出点的权值和。

这个问题具有良好的可合并性，只需记录当前区间中开头结尾选法对应的最大值即可。

现在涉及到修改，由于我们是在前缀和意义下考虑所以修改是一段后缀，直觉上区间修改很难维护，可能只能分块+重构什么的，但还是应该多试试的，有些性质得在编做法的过程中才能发现。

考虑线段树维护上述答案，对于修改 $(t, x, v)$ ：

如果是修改蚂蚁 $S$ ，等价于 $[x,\inf]$ 区间中所有 $P - v$ ， $Q + v$ ，显然我们只需要在当前线段树节点递归到 $x\leq l$ 时快速更新答案即可，那么容易发现影响是 $P .. P$ 会 $- v$ ， $Q ... Q$ 会 $+ v$ ，其他不变，可以直接打 tag。
如果修改方糖 $T$ ，就是让 $[x+L,\inf]$ 中 $P + v$ ， $[x-L,\inf]$ 中 $Q - v$ 。还是考虑线段树递归的过程，递归边界有几种：
- $r < x - L$ ，没影响，直接 return。
- $x+L\leq l$ ，和修改 $S$ 类似，直接打 tag 即可。
- $x-L\leq l,r< x+L$ ，这比较困难，因为这样的区间的四种答案是受到所选 $Q$ 数量的影响的，无脑想法是维护凸包什么的。但我们有性质！注意到这样的区间长度 $\leq x+L-1-(x-L)=2L-1$ ，那么形如 $Q ... P$ 一个点都不会选， $P ... Q$ 最多选一组 $PQ$ ， $P ... P$ 最多选成 $P$ ， $Q ... Q$ 最多选成 $Q$ ，所有的 $Q$ 数量都是固定的，可以直接打 tag 。