Lời giải: Đường đi dài nhất (số điểm dừng tối đa)

Tư duy

An muốn đi từ \(S\) đến \(T\) qua nhiều điểm dừng nhất có thể. Vì bản đồ đảm bảo không có vòng khép kín, ta hoàn toàn có thể:

1. Sắp xếp được các điểm dừng theo một thứ tự đảm bảo sao cho mọi con đường đều đi từ điểm đứng trước sang điểm đứng sau.
2. Tính quy hoạch động trên thứ tự này.

Cách giải

1. Bước 1: Sắp xếp theo thứ tự đảm bảo bằng thuật toán Kahn trong \(O(N + M)\).
2. Bước 2: Gọi dp[v] là số điểm dừng tối đa trên một đường đi hợp lệ từ \(S\) đến \(v\) (bao gồm cả \(S\) và \(v\)). Khởi tạo dp[S] = 1, các dp[v] còn lại ban đầu là \(-\infty\).
3. Bước 3: Duyệt theo thứ tự đảm bảo. Với mỗi điểm \(u\), với mỗi con đường \(u \to v\) cập nhật: \[dp[v] = \max\!\left(\,dp[v],\ dp[u] + 1\,\right)\] Vì khi xét \(u\), mọi điểm có đường đến \(u\) đều đã xử lý, dp[u] đã là số điểm dừng lớn nhất.
4. Kết quả: dp[T] là số điểm dừng lớn nhất trên đường đi từ \(S\) đến \(T\).

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

• Đường đi trên bản đồ không vòng khép kín nghĩa là không thể ghé lại một điểm. Số điểm trên đường đi chính bằng số cạnh cộng \(1\).
• Thứ tự đảm bảo đảm bảo rằng khi xét \(u\), mọi "điểm trước \(u\)" đều đã xử lý. Vậy nên khi cập nhật dp[v], ta đã biết đường đi qua \(u\) với dp[u] điểm là tốt nhất.
• Vì ta cần đến đúng \(T\), đáp án là dp[T].

Đá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<int>> adj(N + 1);
    vector<int> indeg(N + 1, 0);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        indeg[v]++;
    }
    int S, T;
    cin >> S >> T;

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

    const int NEG = -1e9;
    vector<int> dp(N + 1, NEG);
    dp[S] = 1;

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

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