Bài toán vận tải

Buổi 48 — Min-Cost Max Flow
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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 -1 nế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.
Draft saved