网络流
二分图匹配
下面的所有描述均有，对于二分图的两个部(X)、(Y)，(|X|=n)，(|Y|=m)，满足(n leq m)
1、Hall 定理
如果满足二分图有完美匹配，则对于(X)中任意k个点，他们与(Y)连接的点的并集必然不少于k个。
挺显然的。（？）
转化：任意k个其实可以转化成对于所有子段均满足，因为不连续的也可以拆成多个子段。
然后通常来讲这个定理并非直接用的，而是利用这个思想来看看能不能用别的方式来维护。
例题：bzoj 2138 / XSY 3824 U.N.OWEN就是她吗？
↑主要是看到这个题目名字才去写的（
2、最大匹配、最小点覆盖、最大独立集
-
最大匹配不用多说
-
最小点覆盖：覆盖集：一个点集，满足任意一条边至少有一个端点是点集中的点；最小点覆盖=最大匹配（一正一反来证明）
-
最大独立集：独立集：一个点集，其中任意两点没有连边；一个独立集显然是一个覆盖集的补集；最大独立集=总点数-最小点覆盖=总点数-最大匹配
3、经典模型
- 若(X)或(Y)中任意一部，均有每一个点所连的点在另一部上编号连续（l~r），那么可以用堆简单维护：每次贪心选取r最小的。
例：XSY 3899 切割