Chuỗi Cung Ứng Linh Kiện Qua Hai Bậc

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

Một tập đoàn điện tử có $A$ xưởng đúc khuôn, $B$ trạm kiểm định trung gian và $C$ nhà máy đóng gói. Xưởng đúc thứ $i$ sản xuất tối đa $s_i$ lô linh kiện. Trạm kiểm định thứ $j$ chỉ xử lý được tối đa $m_j$ lô linh kiện và tốn phí kiểm định $f_j$ trên mỗi lô. Nhà máy đóng gói thứ $k$ cần nhận tối đa $d_k$ lô linh kiện. Ngoài ra có $E_1$ tuyến vận chuyển từ xưởng đúc sang trạm kiểm định và $E_2$ tuyến từ trạm kiểm định sang nhà máy đóng gói. Biết tập đoàn bắt buộc phải xuất xưởng đúng $K$ lô linh kiện hoàn chỉnh, hãy tìm tổng chi phí (vận chuyển + kiểm định) nhỏ nhất.

Dữ liệu vào

Dòng 1 gồm $A, B, C, K$ ($1 \le A, B, C \le 20, 1 \le K \le 500$). Dòng 2 gồm $A$ số nguyên $s_i$. Dòng 3 gồm $B$ số nguyên $m_j$. Dòng 4 gồm $B$ số nguyên $f_j$. Dòng 5 gồm $C$ số nguyên $d_k$. Dòng 6 gồm $E_1, E_2$. $E_1$ dòng tiếp theo mỗi dòng gồm $u, v, cap, cost$ (xưởng $u$ tới trạm $v$). $E_2$ dòng tiếp theo mỗi dòng gồm $v, w, cap, cost$ (trạm $v$ tới nhà máy $w$).

Dữ liệu ra

In ra tổng chi phí nhỏ nhất để cung ứng đủ $K$ lô linh kiện, hoặc -1 nếu không thể.

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

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

Draft saved