Hall 定理

Hall 定理：

Hall定理：

设一个二分图，V1<=V2。
则V1能完美匹配的条件是，对于所有点集S属于V1，V1能到达V2的点集S2，满足S2>=S1

ex_Hall定理：

设一个二分图，V1<=V2
则，这个图的最大匹配ans=min(|V1-S1|+|S2|)=|V1|-max(|S1|-|S2|)

注意：

其实这里并不在意V1和V2的相对大小，带S进去看就会发现都可以去得到。

例题1：Roundgod and Milk Tea

显然的做法是，我将所有学生看成一类点，所有奶茶看成一类点，学生连线不同班的奶茶，然后直接最大匹配。
但是这样点太多了，考虑用Hall定理直接求解：|V1|-max(|S1|-|S2|)。
我们让V1就是学生的集合，我们现在就是要求max(|S1|-|S2|)，我们设这个值为K。
我们设总共有 suma 的人， sumb 的奶茶
当我 S1 选空时，S2 也为空，K=0。
当我 S1 选择到同一个班（这个班为i ）的学生，S2就是sumb-b( i )，此时就是取max的a( i )-sumb+b( i )，也就是max的a( i )+b( i )
当我 S1 选择到不止一个班，显然S2=sumb，我为了有max(S1-S2)，就要有max(s1-sumb)，此时S1肯定要取到最大suma。
然后用suma-上面三种情况的max即可。

例题2：Exhausted?

这道题是很好的数论+代码练习+思维好题，我会单独写一篇。