Bài toán lập lịch công việc với các ràng buộc phụ thuộc thực chất là bài toán tìm đường đi dài nhất trên Đồ thị có hướng không chu trình (DAG). Mặc dù hướng tiếp cận tiêu chuẩn thường sử dụng Thuật toán Sắp xếp tô pô (Topological Sort) kết hợp với BFS/DFS, chúng ta hoàn toàn có thể giải quyết vấn đề này một cách tối ưu và gọn gàng thông qua tư duy Quy hoạch động (Dynamic Programming).

Phân tích thuật toán

Giả sử dữ liệu đầu vào đảm bảo thứ tự tô pô (tức là các công việc tiên quyết luôn có chỉ số nhỏ hơn công việc hiện tại). Ta có thể định nghĩa trạng thái DP như sau:

• Gọi dp[i] là thời điểm sớm nhất mà công việc i có thể được hoàn thành.
• Công thức chuyển trạng thái: dp[i] = duration[i] + max(dp[j]), trong đó duration[i] là thời gian tự thân của công việc i, và j là tập hợp tất cả các công việc tiên quyết bắt buộc phải hoàn thành trước i.
• Kết quả cuối cùng của bài toán chính là giá trị lớn nhất trong mảng dp sau khi đã tính toán xong toàn bộ các công việc.

Do thứ tự đầu vào đã được sắp xếp, ta có thể tính toán mảng dp trực tiếp ngay trong lúc đọc dữ liệu mà không cần xây dựng cấu trúc đồ thị phức tạp.

Triển khai mã nguồn C++

Dưới đây là đoạn mã đã được cấu trúc lại để xử lý luồng dữ liệu linh hoạt hơn, sử dụng std::stringstream để phân tích cú pháp các điều kiện tiên quyết một cách an toàn:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>

using namespace std;

int main() {
    // Tối ưu hóa I/O trong C++
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int total_tasks;
    if (!(cin >> total_tasks)) return 0;

    // Mảng lưu trữ thời gian hoàn thành sớm nhất của từng công việc
    vector<int> earliest_completion(total_tasks + 1, 0);
    string line;
    
    // Đọc bỏ dòng trống sau khi đọc số lượng công việc
    getline(cin, line); 

    for (int i = 1; i <= total_tasks; ++i) {
        getline(cin, line);
        stringstream ss(line);
        
        int task_id, duration;
        ss >> task_id >> duration;
        
        int max_prereq_time = 0;
        int prereq;
        
        // Đọc các công việc tiên quyết cho đến khi gặp số 0
        while (ss >> prereq && prereq != 0) {
            max_prereq_time = max(max_prereq_time, earliest_completion[prereq]);
        }
        
        // Cập nhật thời gian hoàn thành sớm nhất cho công việc hiện tại
        earliest_completion[task_id] = duration + max_prereq_time;
    }

    // Tìm thời gian hoàn thành lớn nhất trong tất cả các công việc
    int total_time = 0;
    for (int i = 1; i <= total_tasks; ++i) {
        total_time = max(total_time, earliest_completion[i]);
    }

    cout << total_time << "\n";
    return 0;
}

Minh họa quá trình chuyển trạng thái

Để làm rõ cơ chế hoạt động của thuật toán, hãy xem xét một bộ dữ liệu kiểm thử mẫu. Định dạng của mỗi dòng bao gồm: [ID công việc] [Thời gian thực hiện] [Danh sách công việc tiên quyết, kết thúc bằng số 0].

1 3 0
2 9 1 0
3 2 1 2 0
4 2 1 2 3 0
5 12 2 0
6 1 1 2 3 4 5 0
7 17 3 0
8 7 1 2 3 4 5 6 7 0
9 13 1 3 8 0
10 2 1 2 3 4 5 6 7 8 9 0

Dựa trên công thức quy hoạch động, quá trình tính toán mảng dp (hay earliest_completion) sẽ diễn ra tuần tự như sau:

• Công việc 1: Không có công việc tiên quyết. dp[1] = 3.
• Công việc 2: Phụ thuộc vào 1. dp[2] = dp[1] + 9 = 3 + 9 = 12.
• Công việc 3: Phụ thuộc vào 1, 2. dp[3] = max(dp[1], dp[2]) + 2 = max(3, 12) + 2 = 14.
• Công việc 4: Phụ thuộc vào 1, 2, 3. dp[4] = max(dp[1], dp[2], dp[3]) + 2 = max(3, 12, 14) + 2 = 16.
• Công việc 5: Phụ thuộc vào 2. dp[5] = dp[2] + 12 = 12 + 12 = 24.
• Công việc 6: Phụ thuộc vào 1, 2, 3, 4, 5. dp[6] = max(dp[1..5]) + 1 = max(3, 12, 14, 16, 24) + 1 = 25.
• Công việc 7: Phụ thuộc vào 3. dp[7] = dp[3] + 17 = 14 + 17 = 31.
• Công việc 8: Phụ thuộc vào 1 đến 7. dp[8] = max(dp[1..7]) + 7 = max(3, 12, 14, 16, 24, 25, 31) + 7 = 38.
• Công việc 9: Phụ thuộc vào 1, 3, 8. dp[9] = max(dp[1], dp[3], dp[8]) + 13 = max(3, 14, 38) + 13 = 51.
• Công việc 10: Phụ thuộc vào 1 đến 9. dp[10] = max(dp[1..9]) + 2 = max(3, 12, 14, 16, 24, 25, 31, 38, 51) + 2 = 53.