Bài toán vận tải
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Có $S$ nhà máy sản xuất hàng hóa và $D$ kho chứa hàng. Nhà máy thứ $i$ có khả năng cung cấp tối đa $a_i$ tấn hàng, kho thứ $j$ cần nhận đúng $b_j$ tấn hàng.
Chi phí vận chuyển mỗi tấn hàng từ nhà máy $i$ đến kho $j$ là $C_{i,j}$. Hãy tìm tổng chi phí vận chuyển nhỏ nhất để đáp ứng đủ nhu cầu của tất cả $D$ kho. Nếu không thể đáp ứng đủ, in ra -1.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $S, D$ ($1 \le S, D \le 80$).
- Dòng thứ hai chứa $S$ số nguyên $a_1, a_2, \dots, a_S$ ($0 \le a_i \le 10^4$).
- Dòng thứ ba chứa $D$ số nguyên $b_1, b_2, \dots, b_D$ ($0 \le b_j \le 10^4$).
- $S$ dòng tiếp theo, mỗi dòng chứa $D$ số nguyên $C_{i,j}$ ($0 \le C_{i,j} \le 10^4$).
Dữ liệu ra
- In ra tổng chi phí nhỏ nhất, hoặc
-1nếu không đủ nguồn cung.
Ví dụ
| Input | Output |
|---|---|
| 2 3 10 15 8 7 10 4 2 6 3 5 1 |
51 |
Giới hạn
- $1 \le S, D \le 80$.
- Thời gian chạy: 2 giây.
Community Discussion