解题思路

算法概述

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

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贪心验证。

算法步骤

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()

解题思路

本题要求在花费不超过 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)