Lời giải: Thời điểm sớm nhất hoàn thành từng công đoạn

Tư duy

Bài toán yêu cầu với mỗi công đoạn, tìm thời điểm sớm nhất nó có thể hoàn thành, với điều kiện luôn tôn trọng ràng buộc phụ thuộc. Đây chính là bài toán Critical Path Method (Phương pháp đường găng) cổ điển.

Vì thứ tự phụ thuộc đảm bảo không tạo vòng khép kín, ta có thể sắp xếp được các công đoạn theo một thứ tự đảm bảo sao cho mọi ràng buộc đều đi từ công đoạn đứng trước sang công đoạn đứng sau.

Cách giải (Quy hoạch động theo thứ tự đảm bảo)

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: Với mỗi công đoạn \(v\), ta lưu hai giá trị:
   • ES[v] (Earliest Start): thời điểm sớm nhất bắt đầu công đoạn \(v\). \[ES[v] = \max_{(u \to v)} EF[u],\ \text{hoặc}\ 0\ \text{nếu } v\ \text{là công đoạn đầu tiên.}\]
   • EF[v] (Earliest Finish): thời điểm sớm nhất hoàn thành: \[EF[v] = ES[v] + d_v\]
3. Bước 3: Duyệt các công đoạn theo thứ tự đảm bảo:
   • Đầu tiên gán EF[u] = ES[u] + d_u.
   • Sau đó với mỗi ràng buộc \(u \to v\) cập nhật: \[ES[v] = \max\!\left(ES[v],\ EF[u]\,\right)\]
4. Kết quả: In \(EF[1], EF[2], \dots, EF[N]\).

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

Khi duyệt \(u\) theo thứ tự đảm bảo, các công đoạn có ràng buộc đi vào \(u\) đều đã được xử lý (tính xong EF). Do đó khi cập nhật ES[v], giá trị EF[u] ứng với mọi \(u \to v\) đã được tính đúng. Toàn bộ các công đoạn đầu vào đều có ES = 0 và EF = d_v, hoàn toàn khớp với giả định "mọi công đoạn đầu tiên đều bắt đầu ngày 0 và chạy song song".

Đá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<long long> dur(N + 1);
    for (int i = 1; i <= N; ++i) cin >> dur[i];

    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]++;
    }

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

    vector<long long> es(N + 1, 0);
    vector<long long> ef(N + 1, 0);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ef[u] = es[u] + dur[u];
        for (int v : adj[u]) {
            if (ef[u] > es[v]) es[v] = ef[u];
            if (--indeg[v] == 0) q.push(v);
        }
    }

    for (int i = 1; i <= N; ++i) {
        cout << ef[i];
        if (i < N) cout << " ";
    }
    cout << "\n";
    return 0;
}