Phân công hoàn thành sớm nhất

View as PDF
Submit solution
Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có ~n~ người, ~n~ việc ~\left(1 < n \leq 200\right)~. Người thứ ~i~ thực hiện công viêc ~j~ mất ~C[i,j]~ đơn vị thời gian. Giả sử tất cả bắt đầu vào thời điểm ~0~, hãy tìm cách bố trí mỗi công việc cho mỗi người sao cho thời điểm hoàn thành công việc là sớm nhất có thể.

Input

  • Dòng đầu: ~n~
  • Tiếp theo là ma trận ~C[i,j]~. (thuộc kiểu số nguyên ~32-bit~ có dấu)

Output

Ghi thời điểm sớm nhất hoàn thành.

Sample Input

4
10 10 10 2
10 10 3 10
4 10 10 10
10 5 10 10

Sample Output

5

Comments

Please read the guidelines before commenting.


  • 1
    dragon3012009  commented on July 8, 2025, 5:55 p.m. ← edited

    Mình mới tham khảo được một cách tiếp cận khá hay để giải bài toán ghép người với công việc, ngoài phương pháp duyệt DFS tô màu đồ thị. Ta có thể sử dụng kiến thức về luồng cực đại để xử lý bài toán này như sau:

    Ta coi mỗi người là một đỉnh từ 1 đến n, và mỗi công việc là một đỉnh từ n+1 đến 2n.Tạo một đỉnh nguồn là 0 và thu là 2n+1.

    Nối từ nguồn 0 đến mỗi người (1 → n) một cạnh có c = 1 và cũng nối từ mỗi công việc (n+1 → 2n) đến bồn 2n+1 một cạnh cũng có c = 1.Nếu một người có thể làm được một công việc trong thời gian ≤ T, thì nối người đó với công việc đó (giữa đỉnh i và j+n) bằng cạnh có c = 1.

    Với đồ thị như vậy, ta kiểm tra xem với thời gian T có thể ghép được tất cả n người vào n công việc hợp lệ hay không bằng cách tính luồng cực đại từ nguồn đến bồn. Nếu luồng cực đại bằng n thì ta biết là có cách ghép thỏa mãn.

    Ta chặt nhị phân trên T để tìm ra thời gian nhỏ nhất sao cho vẫn có thể ghép được n người.

    Độ phức tạp : O(N * E *E * LogN)

    Code tham khảo : CODE


  • -5
    nguyenlongsamson  commented on Nov. 13, 2024, 7:31 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.