Problem
Bạn cần làm n công việc khác nhau. Trong trường hợp này, bạn có một danh sách n người lao động và giá cả, bao nhiêu đô la mà người lao động làm công việc gì.
Phân phối công nhân sao cho tổng số tiền bạn tiêu ít hơn. Đồng thời, bạn muốn làm mọi thứ trong một ngày, vì vậy các công nhân sẽ làm việc song song. Như vậy, mỗi công nhân sẽ thực hiện đúng một nhiệm vụ.
Đầu vào:
Trong dòng đầu tiên, bạn được cung cấp một số dương n (1 <= n <= 8) - số lượng công việc và công nhân.
N dòng tiếp theo chứa n số nguyên dương được phân tách bằng dấu cách - ma trận A, trong đó A
i,j hiển thị số đô la mà công nhân số i sẽ thực hiện công việc số j. Với mọi A
i,j 1 <= A
i,j <= 10
5.
Đầu ra:
In một số duy nhất - chi phí tối thiểu mà bạn có thể thuê những nhân viên này cho tất cả các công việc có sẵn.
Ví dụ:
| Đầu vào |
Đầu ra |
3
3 1 2
5 6 4
7 8 9
| 12 |
Giải thích:
Công nhân thứ nhất sẽ làm công việc thứ hai, công nhân thứ hai làm công việc thứ ba và công nhân thứ ba làm công việc đầu tiên. Tổng chi phí là 1 + 4 + 7 = 12.