解题思路

算法概述

本题要求在给定的 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)$

DAG路径最小化 · 题解

解法概述

使用二分答案 + 拓扑序DP贪心验证。

贪心正确性证明

引理1：最优解中，每条路径的权值不会超过答案limit，且每个点的调整相互独立。

引理2：对于固定的limit，从拓扑序逆序计算时，每个点需要的最小减少量是确定的。

证明： 考虑点i，设其调整后权值为b_i，其后继点j的调整后权值为b_j。

由于点i到任意后继j的路径权值为 b_i + (该路径上i之后的所有点权和)。

设 g[i] = min_{从i出发的路径} (路径上i之后所有点的调整后权值和)，即从i出发需要满足的上界。

则有约束：b_i + g[i] ≤ limit，即 b_i ≤ limit - g[i]。

从后继递推：设所有从i出发的路径在i之后的部分的最大权值为 h[i] = max_{后继j} g[j]。

则 b_i ≤ limit - h[i]。

为最小化总花费，应取 b_i = min(a_i, limit - h[i])，即尽可能保留原始权值，只在必要时减少。

引理3：上述贪心策略得到的是满足约束的最小总减少量。

证明： 对于每个点i，其可选的调整范围为[0, a_i]，而约束b_i ≤ limit - h[i]强制了上界。取b_i = min(a_i, limit - h[i])使得b_i最大，从而减少量 d_i = a_i - b_i 最小。由于各点的约束相互独立（只通过h[i]传递），最小化各d_i之和即全局最优。

定理：上述贪心算法正确判断limit是否可达。

证明：

• 充分性：若贪心计算的总花费 ≤ x，则存在方案（按贪心结果调整各点）使所有路径权值 ≤ limit。
• 必要性：若存在任何方案使所有路径权值 ≤ limit，则该方案中每个点i的调整后权值b'_i ≤ limit - h[i]，故 b'_i ≤ min(a_i, limit - h[i]) = b_i。调整量 d'_i = a_i - b'_i ≥ a_i - b_i = d_i。因此任何可行方案的总花费 ≥ Σd_i = 贪心计算的花费。

故贪心计算的最少花费等于全局最少花费，算法正确。

参考实现（C++）

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

using ll = long long;
const ll INF = 4e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    ll x;
    if(!(cin >> n >> m >> x)) return 0;
    vector<ll> a(n), c(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> c[i];
    
    vector<vector<int>> g(n);
    vector<int> indeg(n, 0);
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v);
        indeg[v]++;
    }
    
    // 拓扑序
    vector<int> topo;
    topo.reserve(n);
    queue<int> q;
    for(int i = 0; i < n; i++) if(indeg[i] == 0) q.push(i);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for(int v : g[u]) {
            if(--indeg[v] == 0) q.push(v);
        }
    }
    
    // 二分答案
    ll lo = 0, hi = 1e18;
    while(lo < hi) {
        ll mid = (lo + hi) / 2;
        
        // 检查 mid 是否可行
        vector<ll> need(n, 0);  // need[i] = 点i最少需要减掉的权值
        vector<int> outdeg(n, 0);
        for(int u = 0; u < n; u++)
            for(int v : g[u]) outdeg[u]++;
        
        // 从后往前递推
        vector<int> used(n, 0);
        queue<int> qq;
        for(int i = 0; i < n; i++) if(outdeg[i] == 0) qq.push(i);
        
        ll total = 0;
        while(!qq.empty()) {
            int u = qq.front(); qq.pop();
            
            // 计算该点的最大约束
            ll mx = 0;
            for(int v : g[u]) {
                mx = max(mx, need[v]);
            }
            
            // 该点调整后权值上限
            ll limit = mid - mx;
            if(limit < 0) limit = 0;
            
            // 需要的减少量
            ll reduce = max(0LL, a[u] - limit);
            need[u] = reduce;
            total += reduce;
            
            if(total > x) break;
        }
        
        if(total <= x) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    
    cout << lo << "\n";
    return 0;
}

复杂度分析

• 二分：O(log Σa_i)
• 每次验证：O(n + m)（拓扑序）
• 总复杂度：O((n + m) · log Σa_i) ≤ O(500² · log 10⁹) ≈ 10⁶级，轻松通过。

核心思想

将"所有路径权值 ≤ limit"的问题转化为从后往前的贪心递推：每个点需要减多少，取决于它所有后继需要减多少的"压力"。拓扑序保证了DP的正确顺序。

解题思路

使用二分答案 + 拓扑序DP贪心验证。Hard版本数据范围更大，算法复杂度 O(n²) 可通过。

算法步骤

1. 二分最大路径权值上限 X
2. 验证函数 check(X)：从后往前递推每个节点需要减多少权值才能满足约束
3. 统计总花费是否 ≤ x

参考代码（C++17）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    ll x;
    if(!(cin >> n >> m >> x)) return 0;
    vector<ll> 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<int>> g(n + 1), rg(n + 1);
    vector<int> indeg(n + 1, 0);
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        rg[v].push_back(u);
        indeg[v]++;
    }
    
    auto check = [&](ll limit) -> bool {
        vector<ll> need(n + 1, 0);
        queue<int> q;
        for(int i = 1; i <= n; i++)
            if(indeg[i] == 0) q.push(i);
        
        ll total = 0;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            ll cur = max(0LL, need[u]);
            if(a[u] + cur > limit) {
                ll dec = a[u] + cur - limit;
                if(dec * c[u] > x) return false;
                total += dec * c[u];
                if(total > x) return false;
            }
            for(int v : g[u]) {
                need[v] = max(need[v], need[u]);
                if(--indeg[v] == 0) q.push(v);
            }
        }
        return total <= x;
    };
    
    // Restore indeg
    for(int i = 1; i <= n; i++)
        for(int v : g[i]) indeg[v]++;
    
    ll lo = 0, hi = 1e18;
    while(lo < hi) {
        ll mid = (lo + hi) / 2;
        if(check(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
    return 0;
}

解题思路

本题要求在花费不超过 x 的条件下，最小化所有路径权值的最大值。

核心观察

路径的权值上限 X 是否可行，可以通过贪心从后往前递推：

1. 对于终点 v，其所在路径的权值上限为 X，因此 a_v 必须不超过 X
2. 对于其他节点 u，从 u 出发的路径需要满足：a_u + max_child <= X
3. 从拓扑序的逆序递推，可以得到每个节点满足约束所需的最小点权
4. 计算总花费 sum(max(0, a_i - new_a_i) * c_i)，判断是否 <= x

算法步骤

1. 预处理拓扑序，建立反向图
2. 二分答案 X（上界可取所有 a_i 之和）
3. 对每个 X，从后往前递推计算每个节点的最小可行点权
4. 验证所需总花费是否 <= x
5. 二分找到最小的可行 X

时间复杂度

O((n + m) * log(sum a_i))，在 n <= 500 时完全可接受

参考实现 (Python)

import sys
from collections import deque, defaultdict

def solve():
    input = sys.stdin.readline
    n, m, x = map(int, input().split())
    a = list(map(int, input().split()))
    c = list(map(int, input().split()))
    
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        g[u].append(v)
        indeg[v] += 1
    
    order = []
    q = deque([i for i in range(n) if indeg[i] == 0])
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    
    rg = defaultdict(list)
    for u in range(n):
        for v in g[u]:
            rg[v].append(u)
    
    def check(limit):
        need = [0] * n
        for u in reversed(order):
            max_child = 0
            for v in rg[u]:
                max_child = max(max_child, need[v])
            need[u] = max_child
            if need[u] + a[u] > limit:
                need[u] = limit - a[u]
                if need[u] < 0:
                    need[u] = 0
            else:
                need[u] = 0
        
        total_cost = 0
        for i in range(n):
            reduce = a[i] - need[i]
            if reduce > 0:
                total_cost += reduce * c[i]
                if total_cost > x:
                    return False
        return total_cost <= x
    
    lo, hi = 0, sum(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    print(lo)

if __name__ == '__main__':
    solve()