Thuê Đội Robot Lắp Ráp
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Nhà máy tự động hóa có $N$ robot lắp ráp và $N$ dây chuyền sản xuất. Mỗi robot chỉ được gán cho đúng một dây chuyền và mỗi dây chuyền cần đúng một robot vận hành. Khi gán robot thứ $i$ vào dây chuyền thứ $j$, chi phí tiêu thụ điện năng là $C_{i,j}$ (nếu $C_{i,j} = -1$ nghĩa là robot $i$ không tương thích với dây chuyền $j$). Hãy tìm phương án phân công đầy đủ $N$ robot sao cho tổng chi phí điện năng là nhỏ nhất.
Dữ liệu vào
Dòng đầu chứa số nguyên $N$ ($1 \le N \le 40$). $N$ dòng tiếp theo, mỗi dòng gồm $N$ số nguyên $C_{i,j}$ ($-1 \le C_{i,j} \le 1000$).
Dữ liệu ra
In ra tổng chi phí điện năng nhỏ nhất, hoặc -1 nếu không thể phân công đủ $N$ dây chuyền.
Ví dụ
| Input | Output |
|---|---|
| 3 4 2 8 2 3 7 3 1 6 |
10 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion