hall 定理是一个用于判定二分图是否具有完美匹配的定理

Hall 定理是一个用于判定二分图是否具有完美匹配的定理。

Hall 定理则在此基础上给出了一个更强的条件。

Hall 条件用于判断一个二分图是否存在完美匹配。如果对于任意的点集 $T \subseteq X$，均存在：

称此二分图满足 Hall 条件。Hall 定理的表述如下：

考虑到直接枚举子集过于暴力，因此先选择集合中的一个点 $u$，将其删去，将会得到一个更小的子集，这个值已经被提前计算过了，因此一大部分的子集的答案就都被算入其中了。剩下的还未考虑到的子集均包含 $u$，但是除了集合本身外，剩余的子集均会相差至少一个点。因此我们枚举所有集合中的点并去掉，用得到的新的更小的集合的 DP 值来更新当前集合，最后再计算自己是否满足不等式。这样计算的时间是 $O(2^n \cdot n)$ 的。

大致的代码如下：

Hall 定理一般没有什么优化算法复杂度上的用途，但是可以作为一个比较好的思维工具。

例如下面这个问题：

大意是有一个 $n\times m$ 的网格和 $n \times m$ 个人，每个人都要走到一个网格上的一点，每个点只能装下一个人。

同时定义两个点之间的距离为曼哈顿距离，每个人有自己行走的路程上限。

并且注意到它可以递归计算：

并且需要考虑这两条直线的交点是否会占用一个格子。所以我们的做法就是枚举交点，确定是那两条直线相交，并且赋给对应的 $f$ 去，然后对 $f$ 计算后缀和就是我们想要的东西啦～