解题思路

算法概述

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

数据范围扩大到 $n \le 500$，但核心算法不变，仍采用二分答案 + 拓扑序贪心验证。

二分答案

答案具有单调性：若上限 $X$ 可行，则更大的 $X$ 必然可行。单调性二分查找最小可行值。

可行性判断（贪心验证）

贪心策略

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

对于终点节点，若 $a_i > X$，必须将其降到 $X$。

对于其他节点，其所有后继节点 $v$ 的必要降低量 $\text{need}_v$ 已确定，则：

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

正确性证明

引理 1（路径约束传递）：对于任意路径 $P = (v_1, v_2, ..., v_k)$，设 $f_i$ 为从节点 $i$ 出发所有路径的权值上界，则：

$$f_i = \max_{v \in \text{succ}(i)} (a_i' + f_v)$$

证明：由路径定义，从 $i$ 出发的任意路径必须先走某条出边 $(i, v)$，然后继续从 $v$ 出发的路径。取最大值即得最严格约束。 $\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$ 经任意后继 $v$ 的路径，该路径权值为 $a_i' + \sum_{u \in P_v} a_u'$。由约束 $a_i' + \sum_{u \in P_v} a_u' \le X$ 可得 $a_i' \le X - \sum_{u \in P_v} a_u'$。取所有后继路径的下界即得上式。 $\square$

引理 3（拓扑序独立性）：按拓扑逆序计算 $\text{need}_i$ 时，计算结果是唯一确定的。

证明：DAG 中每个节点的 $\text{need}$ 只依赖于其后继的 $\text{need}$。逆拓扑序保证了处理 $i$ 时所有后继已处理完毕，且结果不会再被修改。 $\square$

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

证明：

1. 完整性：算法计算出的 $\{\text{need}_i\}$ 满足所有路径约束（由引理 2 保证）。
2. 最优性：对于每个节点 $i$，$\text{need}_i$ 是满足约束的最小值。若存在更优方案在 $i$ 处花费更少，则减少 $\text{need}_i$ 将导致至少一条从 $i$ 出发的路径权值超过 $X$，矛盾。 $\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);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v});
    }
    
    // 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)$