Thuê Kho Lạnh Lưu Trữ Nông Sản Theo Mùa

Buổi 48 — Min-Cost Max Flow
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Một hợp tác xã nông nghiệp hoạt động trong $N$ tuần liên tiếp. Tuần thứ $i$ thu hoạch thêm $A_i$ tấn nông sản tươi và phải xuất bán đúng $B_i$ tấn cho siêu thị (tổng $\sum A_i = \sum B_i$). Nếu nông sản thu hoạch ở tuần $i$ chưa xuất bán hết, hợp tác xã có thể gửi tối đa $Cap_i$ tấn sang tuần $i+1$ với chi phí cấp đông $Hold_i$ mỗi tấn. Ngoài ra có $M$ hợp đồng chuyển kho nhanh: hợp đồng thứ $k$ cho phép chuyển tối đa $U_k$ tấn từ tuần $x_k$ sang tuần $y_k$ ($x_k < y_k$) với chi phí $Cost_k$ mỗi tấn. Hãy tìm tổng chi phí lưu trữ nhỏ nhất để đáp ứng đủ lượng xuất bán của mọi tuần.

Dữ liệu vào

Dòng 1 gồm hai số nguyên $N, M$ ($2 \le N \le 50, 0 \le M \le 100$). Dòng 2 gồm $N$ số nguyên $A_i$. Dòng 3 gồm $N$ số nguyên $B_i$. Dòng 4 gồm $N-1$ số nguyên $Cap_i$. Dòng 5 gồm $N-1$ số nguyên $Hold_i$. $M$ dòng tiếp theo, mỗi dòng gồm 4 số nguyên $x, y, U, Cost$.

Dữ liệu ra

In ra tổng chi phí nhỏ nhất, hoặc -1 nếu không thể đáp ứng lịch xuất bán.

Ví dụ
Input Output
4 1
5 2 1 2
2 3 2 3
3 2 2
2 3 2
1 4 2 4
11
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved