霍尔定理神仙题

SnowTrace · 2023-09-21 14:00:39 · 题解

神仙题。

首先这个题的二分图匹配做法是比较显然的.

直接设人为左边的点椅子为右边的点直接连边.

这样写即使用前缀优化建图还是会超时.

我们考虑到霍尔定理的一个推论：

二分图的最大匹配数为： |X|-max(|X'|-|N(X')|).

其中 X 为代表所有左部的点，X' 为 X 一个子集，N(X') 为 与 X ' 中点相邻的点的集合.

观察得到本题有一个非常特殊的性质:N(X') 必然是一段前缀与一段后缀的并集.

（因为每一个点的相邻点集合必然是一段前缀和一段后缀的并集）

所以这个题就可以直接被转化成一个数据结构问题。

具体来说，我们从小到大枚举 N(X') 左边那段前缀的长度，对 R 建立线段树，支持区间加和区间最小值，最后算出 |X'|-|N(x')| 的最小值.