AT_arc076_d [ARC076F] Exhausted? 题解 / Hall 定理学习笔记

zrl123456 · 2025-11-12 20:49:47 · 题解

:::::info[题目基本信息] 考察：图论，线段树，扫描线（2819）。
题目简介：
给定一个二分图 G，有 n 个左部点和 m 个右部点，第 i 个右部点的权值为 i，同时给定序列 \{l_n\},\{r_n\}，表示第 i 个左部点会和权值 x 满足 x\le l_i\lor x\ge r_i 的右部点连一条边，现在你可以增加一些右部点并任意钦定他们的权值使得该二分图的最大匹配为 n，问最少添加几个右部点。
数据范围：

1\le n,m\le 2\times 10^5
\forall i\in[1,n],0\le l_i<r_i\le m+1
::::: 显然，本题的答案等价于 n-\nu(G)。
通过尝试众多算法后无果，考虑引入 Hall 定理：
:::::success[Hall 定理]{open} 一个二分图（G=(V_1,V_2,E)，钦定 |V_1|\le|V_2|），设该二分图的最大匹配为 \nu(G)，则 \nu(G)=|V_1| 当且仅当：\forall V\subseteq V_1,|N_G(V)|\ge|V|，其中 N_G(V) 表示在图 G 中 V 的邻居点集合。
::::: :::::success[证明] 我去他的哪个是充分哪个是必要来着。
必要性（后者是前者的必要条件）：
若 \exists V\subseteq V_1,|N_G(V)|<|V|，那么 V 的最大匹配小于 |V|，同时由于，每次 V 新增一个点的过程中最大匹配最多增加 1，故 \nu(G)<|V_1|，与条件矛盾，必要性得证。
充分性（后者是前者的充分条件）：
若存在二分图 \nu(G)<|V_1| 但满足条件 \forall V\subseteq V_1,|N_G(V)|\ge|V|，那么一定有一个左部点不在匹配中，由于满足后者的条件，那么他一定有所连的右部点与其他左部点相连，考虑将这些左部点和原点一起考虑，由于后者条件仍能找到未加进来的右部点，这样不断递归就形成了一条增广路，将其增广可以得到大小为 |V_1| 的匹配，与假设矛盾，充分性得证。

证毕。
Hall 定理还有一条推论：
:::::success[Hall 定理推论]{open}
（引用 Hall 定理内的定义）
$$\nu(G)=
:::::
:::::success[证明]
还是开拆成不等式。
- $\displaystyle\nu(G)\le
对于一子集 V\subseteq V_1 且 $
- $\displaystyle\nu(G)\ge
考虑构造一个新图 G'=(V_1,V_2',E')，其中：
- V_2'=V_2\cup D，其中 D 满足：$
- $E'=E\cup{(u,v)

对于一子集 V\subseteq V_1，它在 G 上的邻居点集 N_{G'}(V)=N_G(V)\cup D，那么：

|N_{G'}(V)|=|N_G(V)\cup D|=|N_G(V)|+\max_{V\subseteq V_1}(|V|-|N_G(V)|)

注意到 |V|\le|N_G(V)|+\displaystyle\max_{V\subseteq V_1}(|V|-|N_G(V)|)=|N_{G'}(V)|，那么由 Hall 定理可知，\nu(G')=|V_1|。
现在将这 \displaystyle\max_{V\subseteq V_1}(|V|-|N_G(V)|) 个点逐一删去，容易发现每次最大匹配最多减少 1，那么我们就得到：

\nu(G)\ge|V_1|-\max_{V\subseteq V_1}(|V|-|N_G(V)|)

大于等于号得证。

原命题得证。
将引理代入得到本题答案为 $\displaystyle\max_{V\subseteq V_1}(
但是区间的并（还是两段）并不好做，所以我们考虑容斥成区间的交，容易得到 \displaystyle\bigcup_{u\in V}[1,l_u]\cup[r_u,m]=m-\bigcap_{u\in V}(l_u,r_u)。
现在考虑枚举交集，但是你好像忘了什么……
- 交集为空集：
这时需要满足条件 \displaystyle\max_{i=1}^nl_i\ge\min_{i=1}^nr_i，最终答案就是 $
- 交集非空：
设交集的开左端点为 L，开右端点为 R，那么开左端点为 L 的答案就是 \displaystyle\max_{R=L+1}^m((\sum_{i=1}^n[l_i\le L\land r_i\ge R])+R-L-1-m)。
这个可以先对 (l_i,r_i) 按第一关键字为 l_i 升序，第二关键字为 r_i 降序的顺序排序，然后就可以上扫描线加线段树做这题了。

然后就做完了。
时间复杂度为 \Theta(n\log n+n\log m+m)，空间复杂度为 \Theta(n+m)。

code