题解：CF2110D Fewer Batteries

· · 题解

图上 DP + 二分答案

根据本题题意，通道为单向边且每条从点 s_i 移动到点 t_i 的通道满足 s_i \lt t_i。

根据这些条件可以确定本题的图是一张 DAG 图，呈现拓扑序，因而我们可以使用图上 DP 来做。

首先本题只需要关注电池数量，电池当前状态是否为充满电的条件其实根本没用，因为每次到达一个点时都直接给已拥有的所有电池充电了，即你拥有的电池永远是满电的。

并且容易发现你在移动的过程中拥有的电池数量单调不降，因为并没有给定 扔掉已拥有的电池 的操作。因而旅程结束时能够拥有的最少电池数量其实就取决于 从点 1 到点 u 的所有路径中经过的边权最大值的最小值，并且你要保证过程中你是可以经过那条边的（即对于 u \to v 的边 w 而言，你要保证到达 u 时拥有的电池数量 + 在 u 点取到的电池数量 \ge w）。

然后我们发现，若旅程结束时能够拥有的最少电池数量为 x，说明拥有 x 个电池能够使得我们从起点 1 到终点 n，而对于拥有 \ge x 个电池时一定也能从起点 1 到终点 n。证明了答案具有单调性，因而可以考虑二分答案来确定这个满足条件的最小的 x。

我们对 x 进行二分答案，其中 x 表示整个过程中拥有的电池数量不会超过 x，也就是说你移动的过程中不可能经过边权 \gt x 的边。

设 f_u 表示表示从点 1 出发且刚到达 u 点且还没获取时 u 位置的能量时拥有的电池数量的最大值（因为要使拥有的能量尽可能小，自然是考虑离开这个位置时才尝试获取该位置能量，即非必要不取该位置的能量）。

由于在二分答案 x 时，我们是考虑在旅程全程中拥有的最少电池数量不超过 x 的情况下能否从点 1 到达点 n。

意味着只需要在走 \le x 的边权下 f_n 处能否可达，只需要考虑最极端最贪的情况即可，即应让 f 数组尽可能取大，由于使用二分求最小了，因而正确性是保证的。

那么初始化 \forall i \in [2,n],f_i \gets - \infty，f_1 \gets 0。

那么我们判定一个 x 是否可行即判定在当前这个 x 下 f_n \ge 0 是否成立。

DP 转移方程：

f_{v}=\max(f_v,\min(x,f_u+power_u))

因为你保证了移动的过程中不可能经过 \gt x 的边，即能发生 DP 转移时已经保证了 x \ge w。

同时为了避免 f_u+power_u 可能超过 x，于是两者取一个最小值即可。

对于二分答案左端点 l=0，右端点 r=10^9+1（用于无解判定），若最终二分的结果为 10^9+1，说明无解。

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