CF2110D Fewer Batteries

题意简述

给定一张 $n$ 个点和 $m$ 条边的有向无环图（DAG），每条边 $(u_i,v_i)$ 保证 $u_i<v_i$，通过时需要电量不少于 $w_i$。

机器人从节点 $1$ 出发，初始电量为 $0$。在到达第 $i$ 个节点时，可以选择获得 $[0,a_i]$ 的电量。求机器人到达节点 $n$ 时的最小电量。

解题思路

答案具有单调性，可以二分最小可行电量 $x$。

由于电量不会减少，全程电量始终不能超过 $x$，显然越早提高电量越好。

设 $f_i$ 表示到达节点 $i$ 时的最大电量，因为 $u_i<v_i$，所以可以直接遍历 $v\in[1,n]$。

考虑节点 $v$，能从所有入边中获得的最大电量为：

$$t=\max_{w(u,v)\le f_u}f_u$$

若不存在满足条件的入边，则令 $t=-\infty$。

该节点能获得的最大电量 $a_v$，总电量不超过 $x$，因此有：

$$f_v=\min(t+a_v,x)$$

最终判断 $f_n\ge 0$ 即表示可行。

每次判断的时间复杂度为 $O(n+m)$，总时间复杂度为 $O((n+m)\log\sum w)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int inf=0x3f3f3f3f3f3f3f3f;
const int N=200005;
vector<pair<int,int>> G[N];
ll a[N],f[N];
bool check(ll x,int n)
{
	f[1]=min(a[1],x);
	for(int v=2;v<=n;v++)
	{
		f[v]=-inf;
		for(auto [u,w]:G[v])
		{
			if(w<=f[u])f[v]=max(f[v],f[u]);
		}
		f[v]=min(f[v]+a[v],x);
	}
	return f[n]>=0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		ll sum=0;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			sum+=a[i];
		}
		while(m--)
		{
			int u,v,w;
			cin>>u>>v>>w;
			G[v].push_back({u,w});
		}
		ll l=0,r=sum+1;
		while(l<r)
		{
			ll mid=l+r>>1;
			if(check(mid,n))r=mid;
			else l=mid+1;
		}
		cout<<(l!=sum+1?l:-1)<<'\n';
		for(int i=1;i<=n;i++)G[i].clear();
	}
	return 0;
}