Lời giải: Đường đi dài nhất có trọng số âm trên DAG

Tư duy

Bài toán này tương tự bài "đường đi có tổng lợi nhuận lớn nhất", nhưng trọng số \(w\) có thể âm (lỗ). Vì hệ đảm bảo không có vòng khép kín, vẫn có thể áp dụng quy hoạch động theo thứ tự đảm bảo, không cần thuật toán Bellman-Ford.

Sự khác biệt so với "đường đi rẻ nhất":

• Trọng số có thể âm → khi khởi tạo, các đỉnh chưa tới được phải là \(-\infty\).
• Ta cần lợi nhuận lớn nhất, nên dùng \(\max\) thay cho \(\min\).

Cách giải

1. Bước 1: Sắp xếp các hoạt động theo một thứ tự đảm bảo (topo sort Kahn) trong \(O(N + M)\).
2. Bước 2: Gọi dp[v] là tổng lợi nhuận lớn nhất để đến được hoạt động \(v\) từ hoạt động \(1\). Khởi tạo dp[1] = 0, các dp[v] còn lại là \(-\infty\).
3. Bước 3: Duyệt theo thứ tự đảm bảo. Với mỗi hoạt động \(u\), với mỗi bước chuyển \(u \to v\) mang lại lợi nhuận \(w\) (có thể âm): \[dp[v] = \max\!\left(\,dp[v],\ dp[u] + w\,\right)\]
4. Kết quả: dp[N] là đáp số cần tìm.

Tại sao thuật toán đúng?

• Vì hệ thống không có vòng khép kín, ta có thể sắp xếp theo thứ tự đảm bảo.
• Khi duyệt \(u\) theo thứ tự đảm bảo, các hoạt động có đường đến \(u\) đã được xử lý, nên dp[u] đã là lợi nhuận lớn nhất.
• Tổng lợi nhuận trên một đường đi chỉ phụ thuộc vào các \(w\) cộng dồn, không có vấn đề "vòng lặp vô hạn" vì không có chu trình.

Đánh giá độ phức tạp

• Sắp xếp: \(O(N + M)\).
• Quy hoạch động: \(O(N + M)\).
• Tổng: \(O(N + M)\) thời gian, \(O(N + M)\) bộ nhớ.

Mã nguồn tham khảo (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<vector<pair<int, long long>>> adj(N + 1);
    vector<int> indeg(N + 1, 0);
    for (int i = 0; i < M; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        indeg[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= N; ++i) {
        if (indeg[i] == 0) q.push(i);
    }

    const long long NEG = -4e18;
    vector<long long> dp(N + 1, NEG);
    dp[1] = 0;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (dp[u] != NEG) {
            for (auto& [v, w] : adj[u]) {
                if (dp[u] + w > dp[v]) {
                    dp[v] = dp[u] + w;
                }
            }
        }
        for (auto& [v, w] : adj[u]) {
            if (--indeg[v] == 0) q.push(v);
        }
    }

    cout << dp[N] << "\n";
    return 0;
}