解题思路

算法概述

本题要求在给定的 DAG 中，通过花费有限的代价降低某些点的权值，使得所有路径的权值（路径上点权之和）的最大值最小。

二分答案

观察到答案具有单调性：若某个上限 $X$ 可行，则所有更大的 $X$ 都可行。因此可以二分最大路径权值的上限。

可行性判断（贪心验证）

贪心策略

从后往前递推每个点至少需要降低多少权值：

对于终点节点（无出边），若其当前权值 $> X$，必须将其降到 $X$。

对于其他节点，设其所有后继节点需要的最小降低量已经确定，则节点 $i$ 至少需要降低：

$$\text{need}_i = \max\left(0, a_i - \left(X - \sum_{v \in \text{succ}(i)} \text{need}_v\right)\right)$$

正确性证明

引理 1（局部最优性）：对于任意节点 $i$，在满足所有以 $i$ 为起点的路径约束的条件下，将 $i$ 的最终权值设为尽可能大不会使后续节点的调整变得更困难。

证明：降低更多只会让约束更容易满足，但会增加不必要的花费。因此在满足约束的前提下，应保持节点权值尽可能高。 $\square$

引理 2（后继需求累积）：节点 $i$ 必须降低的最小量由其所有后继的约束共同决定：

$$\text{need}_i \ge \max\left(0, a_i - \left(X - \sum_{v \in \text{succ}(i)} \text{need}_v\right)\right)$$

证明：每条从 $i$ 出发的路径都要满足权值和 $\le X$。设后继节点的最终权值分别为 $a_v' = \max(0, a_v - \text{need}_v)$，则对于路径 $i \to v \to ...$，有 $a_i' + a_v' + ... \le X$。取所有约束的下界即得上式。 $\square$

引理 3（拓扑序独立性）：按拓扑逆序计算 $\text{need}_i$ 时，一旦 $\text{need}_i$ 被确定，它就不会被后续计算修改。

证明：由于 DAG 的拓扑性质，每个节点的 $\text{need}$ 值只依赖于其后继的 $\text{need}$ 值，而后继在拓扑序中必定排在节点之前。 $\square$

定理（贪心正确性）：上述从后往前的贪心算法能够在 $O(n + m)$ 时间内正确判断是否存在花费不超过 $x$ 的方案。

证明：

1. 可行性：按拓扑逆序处理每个节点 $i$，根据引理 2 计算最小必要降低量 $\text{need}_i$。由于所有后继已处理完成（引理 3），计算出的 $\text{need}_i$ 满足所有从 $i$ 出发的路径约束。
2. 最优性：对于每个节点 $i$，$\text{need}_i$ 是满足约束的最小值。若存在更优方案在 $i$ 处花费更少，则减少 $\text{need}_i$ 将破坏至少一条路径的约束，矛盾。 $\square$

参考代码（C++）

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

struct Edge {
    int to;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    long long x;
    if (!(cin >> n >> m >> x)) return 0;
    
    vector<long long> a(n + 1), c(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    
    vector<vector<Edge>> g(n + 1), rg(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v});
        rg[v].push_back({u});
    }
    
    // Kahn求拓扑序
    vector<int> deg(n + 1, 0);
    for (int u = 1; u <= n; u++)
        for (auto &e : g[u]) deg[e.to]++;
    
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 0) q.push(i);
    
    vector<int> topo;
    topo.reserve(n);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (auto &e : g[u]) {
            if (--deg[e.to] == 0) q.push(e.to);
        }
    }
    
    auto feasible = [&](long long X) -> bool {
        vector<long long> need(n + 1, 0);
        // 逆拓扑序
        for (int i = n - 1; i >= 0; i--) {
            int u = topo[i];
            long long sum = 0;
            for (auto &e : g[u]) sum += need[e.to];
            if (a[u] - sum > X) {
                need[u] = a[u] - sum - X;
            }
        }
        long long total = 0;
        for (int i = 1; i <= n; i++) {
            total += need[i] * c[i];
            if (total > x) return false;
        }
        return total <= x;
    };
    
    long long lo = 0, hi = 1e18;
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
    return 0;
}

复杂度分析

• 时间复杂度：$O((n + m) \cdot \log W)$
• 空间复杂度：$O(n + m)$