Mạng phân phối đa nguồn

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