Phân công công việc
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ nhân viên và $N$ công việc. Nếu giao công việc $j$ cho nhân viên $i$ thì chi phí thực hiện là $A[i][j]$. Mỗi nhân viên chỉ làm đúng một công việc và mỗi công việc chỉ do đúng một nhân viên đảm nhận. Hãy tìm cách phân công sao cho tổng chi phí là nhỏ nhất.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 15$).
- $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên $A[i][j]$ ($0 \le A[i][j] \le 10^6$).
Dữ liệu ra
- In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 3 9 2 7 6 4 3 5 8 1 |
9 |
| 2 1 5 2 4 |
5 |
Giới hạn
- $1 \le N \le 15$
- $0 \le A[i][j] \le 10^6$
Community Discussion