题解：CF2110D Fewer Batteries

lailai0916 · 2025-10-27 16:23:44 · 题解

题意简述

给定一张 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=-\infty。

该节点能获得的最大电量 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;
}