Điều Phối Năng Lượng Vệ Tinh

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

Một trạm không gian cần truyền đúng $K$ đơn vị năng lượng mặt trời từ tấm thu trung tâm (đỉnh $1$) tới kho lưu trữ chính (đỉnh $N$) qua hệ thống $M$ cáp dẫn một chiều. Mỗi cáp dẫn thứ $i$ nối từ nút $u_i$ sang $v_i$ chỉ chịu được tối đa $c_i$ đơn vị năng lượng và gây hao phí nhiệt $w_i$ cho mỗi đơn vị truyền qua. Hãy xác định tổng độ hao phí nhiệt nhỏ nhất để truyền đủ $K$ đơn vị năng lượng tới đỉnh $N$, hoặc in -1 nếu hệ thống không đủ công suất.

Dữ liệu vào

Dòng đầu gồm 4 số nguyên $N, M, K$ ($2 \le N \le 60, 1 \le M \le 200, 1 \le K \le 1000$). $M$ dòng tiếp theo, mỗi dòng gồm 4 số nguyên $u, v, c, w$ ($1 \le u, v \le N, 1 \le c \le 100, 1 \le w \le 1000$).

Dữ liệu ra

In ra một số nguyên duy nhất là tổng hao phí nhiệt tối thiểu, hoặc -1 nếu không thể truyền đủ $K$ đơn vị.

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

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

Draft saved