CF1373F

,

Hall 定理的推论。

题意：

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

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

$n\le 10^6$

Hall 定理的推论

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 定理是等价的。

做法

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

考虑枚举城市的集合 $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");
}