Hall定理

1. Hall 定理

对于一张二分图，设两部分点数为$(x,y)$，则其的一个完备匹配定义为左部分$x$ 个点成为匹配点，特别的，当$x=y$ 的时候这列匹配也称作完备匹配。

一个如上定义的二分图存在完备匹配的充要条件是对于左部分大小为$k$ 的任意子集$S$，这些点在右部连到的点集，记作$N(S)$，的大小不小于$k$，即$|S|\ge |N(S)|$。

证明见： 「学习笔记」Hall定理。

上面就是 Hall 定理，下面是它的推论。

二分图存在大小为$k$ 的匹配，当且仅当$\forall S,|S|\le|N(S)|-k$。

进一步推论：

若使$G$ 中存在完美匹配，则最少补充$\max\{ 0,|S|-|N(S)| \}$ 条边。

我们还有网络流的形式：

设左部点的流量为$a_{i}$，右部点的流量为$b_{i}$，那么有左部点满流，当且仅当$\forall S,\sum_{i\in S} a_i\le \sum_{i\in N_S} b_i$。

最大匹配：

二分图$G$ 的最大匹配为$|S|-\max(|S'|-|N(S')|)$，其中$S$ 为左部点集合，$S'$ 为$S$ 子集。

2.k-正则二分图

k-正则二分图，即所有点度数均为$k$ 的二分图。

k-正则二分图存在$k$ 组不相交的完美匹配，证明考虑 Hall 定理：选出 $a$ 个左部点，他们的度数为 $ak$，连到右部点上，至少有 $k$ 个点，所以此时存在一组完美匹配，删去所有匹配边，k-正则二分图变成了 k-1-正则二分图，归纳即可。

如何快速求出一个 k-正则二分图的完美匹配呢？

利用随机化：

算法如下：

• 重复$N$ 次：
• 随机选一个左边的未匹配点，然后沿增广路随机游走（即从左往右随机走未匹配边，从右往左走匹配边），直到走到一个右边的未匹配点。
• 把走出来的环去掉（找到最后一个出现过多次的点，然后把第一次走到它到最后一次走到它中间的这段路砍掉）。这样就找到了一条增广路。对它进行增广以把匹配数增加$1$。

这样的时间复杂度是$O(n\log n)$。

3. 习题

CF1519F

设$L_x$ 表示第$x$ 个宝箱上所有锁的集合，则对于宝箱选取的集合$S$ 要满足：

$$\sum\limits_{i\in S} a_{i}\le \sum\limits_{j\in \cup_{i\in S} L_{i}} b_{j}$$

这个形式长得很想 Hall 定理的形式，考虑转化，对于每一个宝箱$i$，我们把这个宝箱拆成$a_{i}$ 个点，同理于锁拆成$b_{j}$ 个点。如果宝箱$i$ 上有锁$j$，则将宝箱$i$ 拆出的所有点连一条边到锁 $j$ 拆出的所有点，得到一个二分图，其中宝箱拆成的点在二分图的左部，则要求这个图的左部存在完美匹配（即左部每个点都能和右部的一个点匹配，且匹配点互不相同），下面只需要构造出这个完美匹配即可。

设$f(i,S)$ 表示考虑到第$i$ 个宝箱的点，右部点的锁拆除的点钟还没有被匹配的个数，最少要花费多少。

专一考虑枚举当前宝箱对应匹配上的点，如果匹配上至少一个锁$j$ 拆出的点，则花费的钱要加上$c_{i,j}$，最后取$f(n,*)$ 的最小值即为答案，时间复杂度$O(n\times 5^{2n})$。

ARC076D

用上面补充边的定理，把人看做左部点，而椅子看做右部点，人向$i\in [1,l_{i}] \cup [r_{i},m]$ 连边。

那么节点数为$m-(r-l+1)=m-r+l-1$，由霍尔定理不难得出答案为$|S|-m+r-l+1$。

考虑到数据范围不允许暴力枚举$S$，考虑优化，考虑对右部区间$[L,R]$ 找出对应的做不节点，将人按$l_i$ 升序让后扫描线存储$r_{i}$，将又不借点映射上去，每次将左端点$l$ 的$r_{i}$ 更新入线段树区间加一，让后求$[L,m]$ 的最大值即可。

代码咕咕咕，写太多外部题库的题了？

P3488

显然的二分图完备匹配，但是显然$O(n \log n)$ 直接会直接炸缸，考虑优化。

利用 Hall 定理，令$cnt_{i}$ 表示$[l,r]$ 中$i$ 号码的出现次数，那么满足条件如下：

$$\sum\limits_{i=l}^r cnt_{i}\le k\times (r-k+1+d)$$

进一步化简有：

$$\sum\limits_{i=l}^r cnt_{i}-k \le k \times d$$

维度动态最大子段和即可，时间复杂度$O(m\log n)$。