专栏文章

题解：CF2110D Fewer Batteries

llailai0916qwq
CF2110D题解参与者 1已保存评论 0

文章操作

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

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

题意简述

给定一张 nn 个点和 mm 条边的有向无环图（DAG），每条边 (ui,vi)(u_i,v_i) 保证 ui<viu_i<v_i，通过时需要电量不少于 wiw_i。
机器人从节点 11 出发，初始电量为 00。在到达第 ii 个节点时，可以选择获得 [0,ai][0,a_i] 的电量。求机器人到达节点 nn 时的最小电量。

解题思路

答案具有单调性，可以二分最小可行电量 xx。
由于电量不会减少，全程电量始终不能超过 xx，显然越早提高电量越好。
设 fif_i 表示到达节点 ii 时的最大电量，因为 ui<viu_i<v_i，所以可以直接遍历 v∈[1,n]v\in[1,n]。
考虑节点 vv，能从所有入边中获得的最大电量为：
t=max⁡w(u,v)≤fufut=\max_{w(u,v)\le f_u}f_u
若不存在满足条件的入边，则令 t=−∞t=-\infty。
该节点能获得的最大电量 ava_v，总电量不超过 xx，因此有：
fv=min⁡(t+av,x)f_v=\min(t+a_v,x)
最终判断 fn≥0f_n\ge 0 即表示可行。
每次判断的时间复杂度为 O(n+m)O(n+m)，总时间复杂度为 O((n+m)log⁡∑w)O((n+m)\log\sum w)。

参考代码

CPP
#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;
}

评论

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

正在加载评论...