Vận Chuyển Hàng Hóa Chi Phí Thấp Nhất

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

Một mạng giao thông có hướng gồm $N$ trạm (đánh số từ $1$ đến $N$) và $M$ tuyến đường. Tuyến đường thứ $i$ đi từ $u_i$ đến $v_i$, cho phép vận chuyển tối đa $c_i$ kiện hàng với chi phí $w_i$ cho mỗi kiện hàng.

Bạn cần vận chuyển đúng $K$ kiện hàng từ trạm $1$ đến trạm $N$. Hãy tìm tổng chi phí vận chuyển nhỏ nhất có thể. Nếu không thể vận chuyển đủ $K$ kiện hàng, hãy in ra -1.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $N, M, K$ ($2 \le N \le 200$, $0 \le M \le 2000$, $1 \le K \le 10^6$).
  • $M$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $u_i, v_i, c_i, w_i$ ($1 \le u_i, v_i \le N$, $1 \le c_i \le 10^6$, $0 \le w_i \le 10^6$).
Dữ liệu ra
  • Một số nguyên duy nhất là tổng chi phí nhỏ nhất, hoặc -1 nếu không thể vận chuyển đủ $K$ kiện hàng.
Ví dụ
Input Output
4 5 4
1 2 2 1
1 3 3 2
2 3 1 1
2 4 2 4
3 4 3 1
14
Giới hạn
  • $2 \le N \le 200$, $0 \le M \le 2000$
  • $1 \le K, c_i \le 10^6$, $0 \le w_i \le 10^6$
Draft saved