Hall定理小结

, ,

Hall 定理小结

Hall 定理

对于二分图 $G=(V,E)$ ，令 $N(v)$ 表示与点 $v$ 相邻的点集，则关于最大匹配，我们有如下结论：

设二分图 $G$ 的两部分 $X,Y$，且 $|X|\le |Y|$ ，则 $|X|$ 存在完美匹配（存在一个大小为 $|X|$ 的匹配）当且仅当 $\forall S\subseteq X$，都有 $S\le |N(S)|$。

证明网上很多，这里不再赘述。

推论1

如果一个无向图的每个点度数都为 $k$，则成为其为 $k$ 正则图。

那么左右点数相等的 $k$ 正则二分图必有完美匹配。$k\ge 1$

证明：

若不然，考虑一个左部点集 $L$，则存在 $R=N(L),|R|<|L|$。考虑到 $|R|$ 的所有点的度数和不小于 $|L|\times k$ ，但是 $|R|<|L|$，这与每个点的度数都为 $k$ 矛盾。

推论2

Hall 定理可以用于点有权值的情况。左部点 $i$ 需要匹配 $a_i$ 个右部点，右部点 $i$ 需要匹配 $b_i$ 个左部点。匹配是可重复的。只需要将定理改写一下。其有完美匹配的充要条件为：
$$
\forall S\subseteq X,|\sum\limits_{x\in S}a_x|\le |\sum\limits_{y\in N(S)}b_y|
$$
证明可以将左部点 $i$ 拆成 $a_i$ 个点，右部点同样。发现此条件和原本的 Hall 定理是等价的。

CF1373F Network Coverage

题意：

$n$ 个城市，这 $n$个城市首尾相接形成一个环。每个城市需要 $a_i$ 个网络数量。$n$ 个网络基站，第 $i$ 个网络基站有 $b_i$ 的网络数量，可以给 $i$ 和 $i+1$ 提供 网络。（第 $n$ 个网络基站可以给第 $n$ 座城市和第 $1$ 座城市提供网络）。

判断能否使得所有的家庭都获得网络。

$n\le 10^6$

做法

显然是个带权二分图求完美匹配的题。

考虑枚举城市的集合 $L$，如果 $L$ 不是一个连续的区间，判断其是否合法，与其中每个连续的区间分别同时满足判定的条件是等价的。

转化为对于任意区间 $[l,r]$ ，$\sum\limits_{i=l}^r a_i\le \sum\limits_{i=l-1}^rb_i$ 都成立。

前缀和+后缀最大值即可。题目要求为环的情况，断环为链。

CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int a[maxn],b[maxn],n,d[maxn],suf[maxn];
inline int solve(void) {
	int i,sum1=0,sum2=0;
	read(n);
	for (i=1;i<=n;i++) read(a[i]);
	for (i=1;i<=n;i++) read(b[i]),d[i]=a[i]-b[i],sum1+=d[i];
	if (sum1>0) return puts("NO");
	for (i=1;i<=n;i++) a[i+n]=a[i],b[i+n]=b[i];
	for (i=1;i<=n*2;i++) d[i]=d[i-1]+b[i]-a[i];
	for (suf[n*2+1]=1e18,i=n*2;i>=1;i--) suf[i]=min(suf[i+1],d[i]);
	for (i=1;i<=n;i++) {
		if (suf[i+1]-d[i]+b[i]<0) return puts("NO");
	}
	return puts("YES");
}

推论3

设二分图 $G$ 的两部分分别为 $X,Y$，则最大匹配为 $|X|-\max\limits_{S\subseteq X}(|S|-|N(S)|)$

证明不再赘述。主要是不会

ARC076F

题意

第 $i$ 个人可以与第 $[1,l_i]\bigcup[r_i,m]$ 的凳子相连。求最大匹配。

$n,m\le 2\times10^5$

解法

考虑按 $l_i$ 升序排序。 当前枚举到 $i$。必须去 $i$ ，则：
$$
|X|-\max_{S\subseteq}(|S|-|N(S)|)
=|X|-\max_{S\subseteq X}(|S|+m-\bigcup_{j\in S}(l_i,r_i)
$$
枚举并集，不妨枚举的区间为 $(l_i,k),k>l_i$
$$
n+m-\max_{S\subseteq X}{(\sum\limits_{j\le i}1[l_j\le l_i][k\le r_j]+k-l_i-1})
$$
用线段树维护 $r_j$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
struct node{
	int l,r;
}g[maxn];
inline bool cmp(node x,node y) {return x.l<y.l;}
int n,m;
namespace Seg{
	struct yyy{
		int Max,lazy;
	}f[maxn<<2];
	inline void Pushup(int rt) {f[rt].Max=max(f[rt<<1].Max,f[rt<<1|1].Max);}
	inline void Pushdown(int l,int r,int rt) {
		if (f[rt].lazy) {
			int mid=l+r>>1,k=f[rt].lazy;f[rt].lazy=0;
			f[rt<<1].Max+=k,f[rt<<1|1].Max+=k;
			f[rt<<1].lazy+=k,f[rt<<1|1].lazy+=k;
		}
	}
	inline void Update(int l,int r,int rt,int head,int tail,int k) {
		if (head<=l&&r<=tail) return f[rt].Max+=k,f[rt].lazy+=k,void();
		int mid=l+r>>1;Pushdown(l,r,rt);
		if (head<=mid) Update(l,mid,rt<<1,head,tail,k);
		if (tail>mid)  Update(mid+1,r,rt<<1|1,head,tail,k);
		Pushup(rt); 
	}
	inline int Query(int l,int r,int rt,int head,int tail) {
		if (head<=l&&r<=tail) return f[rt].Max;
		int mid=l+r>>1,tmp1=0,tmp2=0;Pushdown(l,r,rt);
		if (head<=mid) tmp1=Query(l,mid,rt<<1,head,tail);
		if (tail>mid)  tmp2=Query(mid+1,r,rt<<1|1,head,tail);
		return max(tmp1,tmp2);
	}
}
using Seg::Update;
using Seg::Query;
signed main(void){
	int i,ans=0; 
	read(n);read(m);
	for (i=1;i<=n;i++) read(g[i].l),read(g[i].r); 
	sort(g+1,g+1+n,cmp);m++;
	for (i=0;i<=m;i++) Update(0,m,1,i,i,i);
	for (i=1;i<=n;i++) {
		Update(0,m,1,0,g[i].r,1);
		ans=max(ans,Query(0,m,1,g[i].l,m)-g[i].l);
	}
	printf("%d",max(max(0,n-m+1),ans-m));
	return 0;
}

CF338E

题意

$A$ 的长度为 $n$，$B$ 的长度为 $m$。

求 $A$ 有多少长度为 $m$ 的区间中的数和 $B$ 中的数完美匹配。

两个数匹配当且仅当其和不小于 $h$。 (区间必须连续)

$n,m\le 1.5\times 10^5$

解法

顺序与连边无关。考虑将 $B$ 先从大到小排序。那么对于 $a_i$ ，其向 $B$ 连边的节点一定为区间 $[1,l_i]$ 。这是容易计算的。

考虑 Hall 定理。枚举 $N(S)=[1,j]$，则有：
$$
\text{最大匹配}=|X|-\max_{S\subseteq X}(|S|-|N(S)|)=|X|-\max_{S\subseteq X}(\sum\limits 1[l_i\le j]-j)
$$
线段树维护 $l_i$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,m,K;
int a[maxn],b[maxn],r[maxn],g[maxn];
namespace Seg{
	struct yyy{
		int lazy,Max; 
	}f[maxn<<2];
	inline void Pushup(int rt) {f[rt].Max=max(f[rt<<1].Max,f[rt<<1|1].Max);}
	inline void Pushdown(int l,int r,int rt) {
		if (f[rt].lazy) {
			int k=f[rt].lazy;f[rt].lazy=0;
			f[rt<<1].Max+=k,f[rt<<1|1].Max+=k;
			f[rt<<1].lazy+=k,f[rt<<1|1].lazy+=k;
		}
	}
	inline void Update(int l,int r,int rt,int head,int tail,int k) {
		if (head<=l&&r<=tail) return f[rt].lazy+=k,f[rt].Max+=k,void();
		Pushdown(l,r,rt);int mid=l+r>>1;
		if (head<=mid) Update(l,mid,rt<<1,head,tail,k);
		if (tail>mid)  Update(mid+1,r,rt<<1|1,head,tail,k);
		Pushup(rt);
	}
}
using Seg::Update;
int ans=0;
signed main(void){
	int i;
	read(n);read(m);read(K);
	for (i=1;i<=m;i++) read(b[i]);sort(b+1,b+1+m),reverse(b+1,b+1+m);
	for (i=1;i<=m;i++) g[i]=K-b[i];
	for (i=1;i<=n;i++) {
		read(a[i]);
		if (a[i]>=g[1]) r[i]=lower_bound(g+1,g+1+m,a[i]+1)-g-1;
	}
	for (i=0;i<=m;i++) Update(0,m,1,i,i,-i);
	for (i=1;i<=n;i++) {
		if (i>m) {
			Update(0,m,1,r[i-m],m,-1);
		}
		Update(0,m,1,r[i],m,1);
		if (i>=m) {
			if (Seg::f[1].Max==0) ans++;
		}
	}
	printf("%d",ans);
	return 0;
}

可能的例题

  • CF1373G
  • CF1718D