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的正确顺序。