Mạng phân phối đa nguồn
Points
46
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Trên một mạng lưới giao thông có hướng gồm $N$ nút và $M$ tuyến đường, có $P$ nhà máy và $Q$ siêu thị.
- Nhà máy thứ $i$ đặt tại nút $f_i$, sản xuất tối đa $a_i$ sản phẩm với chi phí sản xuất $p_i$ cho mỗi sản phẩm.
- Siêu thị thứ $j$ đặt tại nút $t_j$, cần nhập đúng $b_j$ sản phẩm.
- Mỗi tuyến đường $(u, v)$ có sức chứa $cap$ và chi phí vận chuyển $cost$ cho mỗi sản phẩm.
Hãy tìm tổng chi phí (sản xuất + vận chuyển) nhỏ nhất để đáp ứng đủ nhu cầu của tất cả siêu thị, hoặc in ra -1 nếu không thể.
Dữ liệu vào
- Dòng đầu tiên chứa bốn số nguyên $N, M, P, Q$ ($2 \le N \le 300, 1 \le M \le 3000, 1 \le P, Q \le 50$).
- $P$ dòng tiếp theo, mỗi dòng chứa $f_i, a_i, p_i$.
- $Q$ dòng tiếp theo, mỗi dòng chứa $t_j, b_j$.
- $M$ dòng cuối cùng, mỗi dòng chứa $u, v, cap, cost$.
Dữ liệu ra
- In ra tổng chi phí nhỏ nhất, hoặc
-1nếu không thể.
Ví dụ
| Input | Output |
|---|---|
| 4 4 2 2 1 10 2 2 10 5 3 8 4 6 1 3 10 3 1 4 5 4 2 3 10 1 2 4 10 1 |
76 |
Giới hạn
- $2 \le N \le 300, 1 \le M \le 3000$.
- Thời gian chạy: 2 giây.
Community Discussion