Gửi đúng K đơn hàng

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

Một công ty cần vận chuyển chính xác $K$ đơn hàng từ kho trung tâm (đỉnh $1$) đến cảng xuất khẩu (đỉnh $N$) qua mạng lưới giao thông có hướng gồm $N$ nút và $M$ tuyến đường.

Mỗi tuyến đường $(u, v)$ cho phép chở tối đa $cap$ đơn hàng với chi phí $cost$ cho mỗi đơn hàng. Hãy tìm tổng chi phí nhỏ nhất để gửi đủ $K$ đơn hàng. Nếu không thể gửi đủ $K$ đơn hàng, 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, 1 \le M \le 2000, 0 \le K \le 10^4$).
  • $M$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $u, v, cap, cost$ ($1 \le u, v \le N$, $1 \le cap \le 10^4$, $0 \le cost \le 10^4$).
Dữ liệu ra
  • In ra một số nguyên duy nhất là chi phí nhỏ nhất, hoặc -1 nếu không thể gửi đủ $K$ đơn hàng.
Ví dụ
Input Output
4 5 4
1 2 3 2
1 3 2 4
2 3 1 1
2 4 2 5
3 4 3 1
21
Giới hạn
  • $2 \le N \le 200, 1 \le M \le 2000, 0 \le K \le 10^4$.
  • Thời gian chạy: 2 giây.
Draft saved