定理内容
对于二分图中的集合 X和 Y（|X|≤|Y|），任取一个 X的子集 s（s⊆X），设 Y中与 s有边相连的点集为 N(s)，若 X和 Y存在完美匹配（完美匹配指的是匹配数 =|X|），则一定满足 |s|≤|N(s)|
反之亦然，即这是该图存在完美匹配的充要条件
（中文音译叫霍尔定理）
正确性证明
必要性
若某个奇妙♂の图存在完美匹配，且不满足 Hall 定理
那么就有 k个点，连出去的点不足 k个
那谁跟它们匹配吖？
_(:зゝ∠)_
充分性
若某个奇妙♂の图不存在完美匹配，且满足 Hall 定理
那么它的最大匹配状态下，至少有一个点 a未匹配
根据 Hall 定理，有至少一个和它相连的对面的点 b
若这个点 b不在最大匹配中，那。。。ab就能匹配了呀
所以点 b在最大匹配中，那么一定有一个点 c与点 b匹配
根据霍尔定律，Y中与 a和 c相连的点的数目 ≥2，因此除了点 b外，一定至少还有一个点与点 c相邻。。。
这样下去就一定能找到一条增广路，与一开始我们假设的条件矛盾，因此得证
例题
「2017 山东一轮集训 Day2」Pair LOJ – 6062
由于 a,b是独立的，因此可以看成二分图
由于 b的顺序与答案无关，因此可以先把 b从小打到排个序
设当前枚举的连续的一段 a的子数列为集合 X
对于 bi来说，X中与 b1,b2,b3,…,bi–1相邻的点都一定与 bi相邻
因此在 b中选择一个子集 k，若 bi是 k中最大元素，那么 |N(k)|就等于 X中与 bi相邻的点数，且 |k|的最大取值就是 i，需要满足 |N(k)|≥|k|
也就是说要求 X中与 bi相邻的点数要 ≥i
所以我们要维护 X中与 bi相邻的点数
注意到对于每个 ai，与其相邻的点集是 b的一个连续后缀，因此可以用线段树维护
代码：
#include <bits/stdc++.h>
#define NS (150005)
#define LS(a) ((a) << 1)
#define RS(a) ((a) << 1 | 1)
using namespace std;
template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}
int n, m, h, A[NS], B[NS], ans;
struct N {int mn, tag;} e[NS << 2];
void pup(int a) { e[a].mn = min(e[LS(a)].mn, e[RS(a)].mn); }
void pdown(int a)
{
if (!e[a].tag) return;
int l = LS(a), r = RS(a);
e[l].mn += e[a].tag, e[l].tag += e[a].tag;
e[r].mn += e[a].tag, e[r].tag += e[a].tag;
e[a].tag = 0;
}
void build(int l, int r, int a)
{
if (l == r) { e[a].mn = -l; return; }
int mid = (l + r) >> 1;
build(l, mid, LS(a)), build(mid + 1, r, RS(a)), pup(a);
}
void add(int l, int r, int d, int L, int R, int a)
{
if (l <= L && R <= r) { e[a].mn += d, e[a].tag += d; return; }
pdown(a);
int Mid = (L + R) >> 1;
if (l <= Mid) add(l, r, d, L, Mid, LS(a));
if (r > Mid) add(l, r, d, Mid + 1, R, RS(a));
pup(a);
}
int main(int argc, char const* argv[])
{
IN(n), IN(m), IN(h);
for (int i = 1; i <= m; i += 1) IN(B[i]);
for (int i = 1; i <= n; i += 1) IN(A[i]);
sort(B + 1, B + 1 + m), build(1, m, 1);
for (int i = 1; i < m; i += 1)
{
int j = lower_bound(B + 1, B + 1 + m, h - A[i]) - B;
if (j <= m) add(j, m, 1, 1, m, 1);
}
for (int i = m; i <= n; i += 1)
{
int j = lower_bound(B + 1, B + 1 + m, h - A[i]) - B;
if (j <= m) add(j, m, 1, 1, m, 1);
if (e[1].mn >= 0) ans++;
j = lower_bound(B + 1, B + 1 + m, h - A[i - m + 1]) - B;
if (j <= m) add(j, m, -1, 1, m, 1);
}
printf("%d\n", ans);
return 0;
}
5 条评论
Fideow · 2022年2月11日 9:49 下午
那个，大佬，充分性的证明是不是假了？正解应该是归纳假设吧。。。？
HS · 2020年4月9日 8:11 下午
%%%
Qiuly · 2019年2月28日 10:44 上午
%%%Tql
饕餮传奇 · 2019年2月28日 9:18 上午
赞一个
Rayment · 2019年3月2日 2:53 下午
前排捕捉