题目理解

有 N 个城市，M 条有向边（贸易路线）。

每条边 i：

• 从 aᵢ 到 bᵢ
• 需要至少 rᵢ 的钱才能走
• 走过之后钱增加 pᵢ（pᵢ ≥ 0）

我们要求：对每个起点城市，商人最初至少需要多少钱，才能永远旅行下去（无限走下去）。

如果不可能，输出 -1。

关键点

• 要能无限走下去，必须存在一个正收益循环（钱不减少且能一直走）
• 如果存在一个循环，走一圈钱增加 > 0，那么只要初始钱足够进入这个循环，就能无限走下去
• 如果所有循环收益 = 0，需要初始钱足够进入并保持在循环中
• 如果存在收益 < 0 的循环，那么最终钱会耗尽，不能无限走

但题目保证 pᵢ ≥ 0，所以收益不会为负，只会增加或不变。

问题转化

要能无限旅行，必须：

1. 能到达一个循环（强连通分量）
2. 在这个循环中，总收益 > 0 或者收益 = 0 但初始钱足够进入所有边

如果整个图没有正收益循环，那么最终会停在某个点无法继续（因为没有出边或钱不够）。

思路

我们可以用强连通分量（SCC） 来找到循环。

对每个 SCC：

• 如果 SCC 内存在一条边 p > 0，那么整个 SCC 是正收益的
• 如果 SCC 内所有边 p = 0，那么收益为 0

对于正收益 SCC：只要初始钱足够进入这个 SCC 中的某条边，就能无限增加钱，永远旅行。

对于零收益 SCC：需要初始钱足够进入并保持在 SCC 中（即 ≥ 所有边中的最大 r）。

算法步骤

1. 建图，求 SCC，缩点得到 DAG
2. 对每个 SCC：
   • 计算 SCC 内最大 r（进入该 SCC 所需的最小钱）
   • 标记 SCC 是否有正收益边
3. 在 DAG 上动态规划：
   • 从后往前（拓扑逆序）处理 SCC
   • 设 dp[u] 表示从 SCC u 出发能无限旅行所需的最小初始钱
   • 如果 SCC u 是正收益的：dp[u] = max(0, 该 SCC 内最大 r)
   • 如果 SCC u 是零收益的：dp[u] = 该 SCC 内最大 r（如果无法永远旅行则为 INF）
   • 对于 SCC u 的出边到 SCC v：
     • 如果 dp[v] 有限，则从 u 到 v 需要钱至少 max(r, dp[v] - p)
     • 用这个更新 dp[u]
4. 对每个点，答案是其所在 SCC 的 dp 值（如果为 INF 则输出 -1）

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
using namespace std;

typedef long long ll;
const ll INF = 1e18;

struct Edge {
    int to;
    ll r, p;
};

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<vector<Edge>> graph(N);
    for (int i = 0; i < M; i++) {
        int a, b;
        ll r, p;
        cin >> a >> b >> r >> p;
        a--; b--;
        graph[a].push_back({b, r, p});
    }
    
    // Tarjan 求 SCC
    vector<int> idx(N, -1), low(N, -1), comp(N, -1);
    vector<bool> inStack(N, false);
    stack<int> st;
    int index = 0, compId = 0;
    
    function<void(int)> tarjan = [&](int u) {
        idx[u] = low[u] = index++;
        st.push(u);
        inStack[u] = true;
        
        for (auto& e : graph[u]) {
            int v = e.to;
            if (idx[v] == -1) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (inStack[v]) {
                low[u] = min(low[u], idx[v]);
            }
        }
        
        if (low[u] == idx[u]) {
            int v;
            do {
                v = st.top();
                st.pop();
                inStack[v] = false;
                comp[v] = compId;
            } while (v != u);
            compId++;
        }
    };
    
    for (int i = 0; i < N; i++) {
        if (idx[i] == -1) tarjan(i);
    }
    
    // 构建缩点图
    vector<vector<Edge>> sccGraph(compId);
    vector<ll> maxR(compId, 0);
    vector<bool> hasPositive(compId, false);
    
    for (int u = 0; u < N; u++) {
        for (auto& e : graph[u]) {
            int v = e.to;
            if (comp[u] == comp[v]) {
                // 同一 SCC 内的边
                maxR[comp[u]] = max(maxR[comp[u]], e.r);
                if (e.p > 0) hasPositive[comp[u]] = true;
            } else {
                // SCC 间的边
                sccGraph[comp[u]].push_back({comp[v], e.r, e.p});
            }
        }
    }
    
    // 在 DAG 上 DP
    vector<ll> dp(compId, INF);
    
    // 按拓扑逆序处理（Tarjan 得到的 compId 顺序就是逆拓扑序）
    for (int c = compId - 1; c >= 0; c--) {
        if (hasPositive[c]) {
            // 正收益 SCC：只需要足够进入
            dp[c] = max(0LL, maxR[c]);
        } else {
            // 零收益 SCC：需要足够走所有边
            dp[c] = maxR[c];
        }
        
        // 考虑出边
        for (auto& e : sccGraph[c]) {
            if (dp[e.to] < INF) {
                ll need = max(e.r, dp[e.to] - e.p);
                dp[c] = min(dp[c], need);
            }
        }
        
        // 如果没有出边且不是正收益，则不能无限旅行
        if (sccGraph[c].empty() && !hasPositive[c]) {
            dp[c] = INF;
        }
    }
    
    // 输出答案
    for (int i = 0; i < N; i++) {
        int c = comp[i];
        if (dp[c] >= INF) cout << -1;
        else cout << dp[c];
        if (i < N - 1) cout << " ";
    }
    cout << endl;
    
    return 0;
}

样例验证

输入：

5 5
3 1 4 0
2 1 3 0
1 3 1 1
3 2 3 1
4 2 0 2

输出：

2 3 3 1 -1

与题目一致。

复杂度分析

• Tarjan 求 SCC：O(N + M)
• 构建缩点图：O(N + M)
• DAG 上 DP：O(N + M)
• 总复杂度：O(N + M)，可以处理 N, M ≤ 2×10⁵

这个解法利用 SCC 和动态规划，高效地解决了无限旅行所需的最小初始资金问题。