#5397. Giao việc (Mã bài: ASSIGNMENT)

Có công nhân và công việc. Nếu công nhân được giao thực hiện công việc , chi phí để hoàn thành là . Mỗi công nhân chỉ có thể làm một công việc và mỗi công việc chỉ cần một công nhân.

Yêu cầu: Hãy tìm một cách phân công công việc cho các công nhân sao cho tổng chi phí để hoàn thành tất cả các công việc là nhỏ nhất.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên .
• dòng tiếp theo, tạo thành một ma trận chi phí kích thước . Số ở hàng cột là chi phí .

Kết quả: Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ví dụ:

Dữ liệu:

3
9 2 7
6 4 3
5 8 1

Kết quả:

9

Giải thích: Cách phân công tối ưu:

• Công nhân 1 làm việc 2 (chi phí 2).
• Công nhân 2 làm việc 1 (chi phí 6).
• Công nhân 3 làm việc 3 (chi phí 1).

Tổng chi phí: .

Dữ liệu:

3
25 40 35
40 60 35
20 40 25

Kết quả:

100

Dữ liệu:

3
8 2 5
3 2 7
4 6 8

Kết quả:

13

Giới hạn:

• .
• .