hall 定理

031@2x.gif (56×56) (emojiall.com) 074@2x.gif (56×56) (emojiall.com) 027@2x.gif (56×56) (emojiall.com) 081@2x.gif (56×56) (emojiall.com)

霍尔定理

假设现在有二分图，其左部点集合为 $S$ ，右部点集合为 $T$ ，我们钦定 $|S|\le|T|$ ，设 $state(S)$ 表示若选出的左部点集合为 $S$ ，他们连向的右部点的集合为 $state(S)$ 。霍尔定理就是：若 $\prod\limits_{T \in S} [|T|\le |state(T)|]=1$ ，则该图有完美匹配，否则没有。

证明可以看这里 ~~其实这里讲的比我好多了~~

现在有几个推广

若二分图的匹配边数量为 $|S|-k$ ，则 $\prod\limits_{T \in S} [|T|-k\le |state(T)|]=1$ ，反之同理。~~证明还是可以看上面的链接~~
若现在一个左部点 $x$ 可以匹配 $l(x)$ 个右部点，一个右部点 $y$ 可以匹配 $r(y)$ 个右部点，则存在现定义下的完美匹配的充要条件为 $\prod\limits_{T \in S} [\sum\limits_{x\in T} l(x) \le \sum\limits_{y \in state(T)}r(y)]=1$ ，这个的证明大概就是把一个左部点 $x$ 拆成 $l(x)$ 个左部点，这样就和霍尔定理一样了

然后是题目：

Loj #6062. 「2017 山东一轮集训 Day2」Pair

假设我们已经确定了一个左部点集合 $S$ ，设右部点集合为 $T$ ，考虑怎么快速 $chk$ 这个集合是否有完美匹配，考虑霍尔定理，直接做显然不现实，分析性质发现：如果霍尔定理枚举到的集合为 $S$ ，若 $x,y\in S,a_x\le a_y$ ，则所有 $x$ 与右部点连的边都被 $y$ 与右部点连的边包含了，所以对于一个左部点集合 $S$ ，向右部点连的边数可以直接算最大值向右部点连的边数，假设我们设 $a_x$ 是集合中最大的元素， $a_x$ 在集合中的排名为 $k$ ，不难发现 $|S| \le k$ ，所以现在这个集合有完美匹配的充要条件就是 $\prod\limits_{x\in S}[\sum\limits_{y\in T}[a_x+a_y\ge h]\ge k_x]=1$ ，其中 $k_x$ 表示元素 $x$ 在集合 $S$ 中的排名，内部的 $\sum$ 可以用 $lower\_bound$ 来解决，所以现在 $chk$ 一个集合的复杂度已经被我们缩小到 $O(n\log n)$ 了。

现在考虑题目让求的怎么做，发现从一个集合移动到下一个集合只是删掉一个元素再加上一个元素，考虑有 $ds$ 维护这个东西，因为我们需要求出排名，所以肯定是需要维护有序序列的，又因为要支持加入删除，这肯定要更改这个数后面的排名，就是一个区间修改，这样我们就排除了堆等一些简单的 $ds$ ，发现上面说的操作很线段树，考虑维护一颗线段树，对于第 $i$ 个位置维护排序后的第 $i$ 大（不去重），维护这个点现在在不在 $S$ 中，和式子 $\prod\limits_{x\in S}[\sum\limits_{y\in T}[a_x+a_y\ge h]\ge k_x]=1$ 的值，大概操作方法就是删掉位置 $i$ 的数就让 $[i+1,n]$ 的数全部加 $1$ （这个加 $1$ 的原因是后面的 $k$ 全部减了 $1$ ，所以式子的值要加 $1$ ），加数同理，不难维护。

code

CF1519F Chests and Keys

~~这数据范围真离谱~~

建一个类似于费用流的东西，源点向所有宝箱连一条容量为 $a_i$ 的边，每个钥匙向汇点连一条容量为 $b_i$ 的边，将“在第 $i$ 个箱子上上上第 $j$ 个锁“看成让左部点 $i$ 向右部点 $j$ 连一条容量为 $INF$ 的边，费用为 $c_{i,j}$ ，不难发现一种连边方法合法等于 $\sum\limits_{T\in S}[\sum\limits_{x\in T}a_x\le\sum\limits_{y\in state(T)}sum(T,y)]$ ，其中 $S$ 为所有宝箱构成的集合， $state$ 和 $sum$ 和上面写的意思一样，发现这玩意就是霍尔定理推广 $2$ ，所以现在就等于要找到一张花费最小的有完美匹配的图。