专栏文章

题解：CF2110D Fewer Batteries

MMeickol
CF2110D题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minz21e1
此快照首次捕获于
2025/12/02 10:41
3 个月前
此快照最后确认于
2025/12/02 10:41
3 个月前
查看原文

图上 DP + 二分答案

根据本题题意，通道为单向边且每条从点 sis_i 移动到点 tit_i 的通道满足 si<tis_i \lt t_i。
根据这些条件可以确定本题的图是一张 DAG 图，呈现拓扑序，因而我们可以使用图上 DP 来做。
首先本题只需要关注电池数量，电池当前状态是否为充满电的条件其实根本没用，因为每次到达一个点时都直接给已拥有的所有电池充电了，即你拥有的电池永远是满电的。
并且容易发现你在移动的过程中拥有的电池数量单调不降，因为并没有给定 扔掉已拥有的电池 的操作。因而旅程结束时能够拥有的最少电池数量其实就取决于 从点 11 到点 uu 的所有路径中经过的边权最大值的最小值，并且你要保证过程中你是可以经过那条边的（即对于 u→vu \to v 的边 ww 而言，你要保证到达 uu 时拥有的电池数量 + 在 uu 点取到的电池数量 ≥\ge ww）。
然后我们发现，若旅程结束时能够拥有的最少电池数量为 xx，说明拥有 xx 个电池能够使得我们从起点 11 到终点 nn，而对于拥有 ≥x\ge x 个电池时一定也能从起点 11 到终点 nn。证明了答案具有单调性，因而可以考虑二分答案来确定这个满足条件的最小的 xx。
我们对 xx 进行二分答案，其中 xx 表示整个过程中拥有的电池数量不会超过 xx，也就是说你移动的过程中不可能经过边权 >x\gt x 的边。
设 fuf_u 表示表示从点 11 出发且刚到达 uu 点且还没获取时 uu 位置的能量时拥有的电池数量的最大值（因为要使拥有的能量尽可能小，自然是考虑离开这个位置时才尝试获取该位置能量，即非必要不取该位置的能量）。
由于在二分答案 xx 时，我们是考虑在旅程全程中拥有的最少电池数量不超过 xx 的情况下能否从点 11 到达点 nn。
意味着只需要在走 ≤x\le x 的边权下 fnf_n 处能否可达，只需要考虑最极端最贪的情况即可，即应让 ff 数组尽可能取大，由于使用二分求最小了，因而正确性是保证的。
那么初始化 ∀i∈[2,n],fi←−∞\forall i \in [2,n],f_i \gets - \infty，f1←0f_1 \gets 0。
那么我们判定一个 xx 是否可行即判定在当前这个 xx 下 fn≥0f_n \ge 0 是否成立。
DP 转移方程：
fv=max⁡(fv,min⁡(x,fu+poweru))f_{v}=\max(f_v,\min(x,f_u+power_u))
因为你保证了移动的过程中不可能经过 >x\gt x 的边，即能发生 DP 转移时已经保证了 x≥wx \ge w。
同时为了避免 fu+poweruf_u+power_u 可能超过 xx，于是两者取一个最小值即可。
对于二分答案左端点 l=0l=0，右端点 r=109+1r=10^9+1（用于无解判定），若最终二分的结果为 109+110^9+1，说明无解。
CPP
const int N=2e5+5;
int n,m;
int power[N];
vector<array<int,2> > E[N];
int f[N]; // f[u] 表示刚到达 u 点且还没获取该位置能量的最大值（考虑离开这个位置时才尝试获取该位置能量）
bool check(int x){
	int INF;
	memset(&INF,0x3f,sizeof INF);
	rep(i,1,n) f[i]=-INF;
	f[1]=0;
	rep(u,1,n){
		for(auto t:E[u]){
			int v=t[0],w=t[1];
			if(w>x) continue;
			if(f[u]+power[u]>=w){
				f[v]=max(f[v],min(x,f[u]+power[u]));
			}
		}
	}
	return f[n]>=0;
	// rep(i,1,n) cout<<f[i]<<" ";
	// cout<<endl;
}
void solve(){
	cin>>n>>m;
	rep(i,1,n) E[i].clear();
	rep(i,1,n) cin>>power[i];
	rep(i,1,m){
		int a,b,c;
		cin>>a>>b>>c;
		E[a].push_back({b,c});
	}
	int l=0,r=1e9+1;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	if(r==1e9+1) cout<<-1;
	else cout<<l;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...