夏晓光(loveJY)的博客

终于不是构造题了

但是还是判断是否有解的那种细节题/...

首先我们有一个网络流暴力做法

虽然这个图很特殊,但是仍然可能会TLE,如果认真卡卡的话,势能让增广次数很多很多的

然后考虑优化这个过程,我们没有很好利用这个图的性质才导致我们增广次数可能很多吧

构造开始

1. 让$a_1$尽可能的分给$b_1$然后剩下的再分给$b_2$

这样保证了$a_n$尽可能少用,但是为什么呢?

2. 如果有一个在用了$a_{i-1},a_{i}$后仍然没有填满,我们就从$a_n$调一些流量过来,然后把沿路上所有的分配都改掉

这个也很显然,对应了1的操作

但是改掉是改啥啊

你会发现$a_i$如果想$b_i$分配了流量,我们就可以减少一点这个流量,让$a_i$给$b_{i+1}$多分配一点流量

然后重复这个过程就能最后让我们被限制住的那个点多一点流量

所以你会发现这个过程限制住的是我们中途那些i正好向i流量的边所流出的流量最小值

那么我们所有这样的取个min就是现在处理点i能调过来的权值了qwq

同样的,我们别忘了这个min-新调过去的权值

然后我们之后可能又有一些i向i流的边成为新限制,所以这个限制是动态加入的

3. 最后判断n能否合法即可

即$a_n>=b_n$

如果我们从$a_n$调了过多的流量他会变成负数....

code:

代码写了很多细节,但是由于写过藤原千花所以完全不虚(只需要写个网络流对拍....)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+7;
int T;
int n;
int a[MAXN],b[MAXN];

inline void solve() {
	int tmp1=min(b[1],a[1]);
	if(b[1]<=a[1]) {
		a[1]-=b[1];
		b[1]=0;
	} else {
		b[1]-=a[1];
		a[1]=0;
		if(b[1]>a[n])return (void)puts("NO");
		else {
			a[n]-=b[1];
			b[1]=0;
		}
	}
	if(a[1]>0) {
		if(b[2]<=a[1]) {
			a[1]-=b[2];
			b[2]=0;
		} else {
			b[2]-=a[1];
			a[1]=0;
		}
	}
	int tmp2=a[n];
	for(int i=2; i<n; ++i) {
		if(b[i]<=0) {
			b[i+1]-=a[i];
			tmp1=0;
		} else {
			if(b[i]<=a[i]) {
				a[i]-=b[i];
				tmp1=min(tmp1,b[i]);
				b[i+1]-=a[i];
			} else {
				b[i]-=a[i];
				if(b[i]>a[n]) {
					return (void)puts("NO");
				} else {
					a[n]-=b[i];
					b[i]=0;
					if(tmp2-a[n]>tmp1)return (void)puts("NO");
					tmp1-=tmp2-a[n];
					tmp2=a[n];
				}
				tmp1=min(tmp1,a[i]);
				a[i]=0;
			}
		}
	}
	if(a[n]>=b[n])return (void)puts("YES");
	else return (void)puts("NO");
}

int main() {
	scanf("%d",&T);
	while(T-->0) {
		scanf("%d",&n);
		for(int i=1; i<=n; ++i)scanf("%d",&b[i]);
		for(int i=1; i<=n; ++i)scanf("%d",&a[i]);
		solve();
	}
	return 0;
}

/*
1
10
5 5 3 5 1 2 3 5 3 3
5 3 5 2 2 4 3 4 5 3
*/