Tưới tiêu khu vườn

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

Hệ thống ống dẫn nước gồm $N$ nút và $M$ ống dẫn có hướng. Ống dẫn thứ $i$ nối từ $u$ đến $v$ có sức chứa tối đa $cap_i$ và hệ số ma sát $a_i$. Nếu truyền $f$ đơn vị nước ($0 \le f \le cap_i$) qua ống này, năng lượng tiêu tốn là $a_i \cdot f^2$.

Hãy tìm tổng năng lượng nhỏ nhất để dẫn $K$ đơn vị nước từ nút $1$ đến nút $N$, hoặc in ra -1 nếu không thể.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $N, M, K$ ($2 \le N \le 100, 1 \le M \le 500, 1 \le K \le 100$).
  • $M$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $u, v, cap_i, a_i$ ($1 \le cap_i \le 10, 0 \le a_i \le 100$).
Dữ liệu ra
  • In ra tổng năng lượng nhỏ nhất, hoặc -1 nếu không thể.
Ví dụ
Input Output
3 3 3
1 2 3 1
1 3 2 2
2 3 3 1
10
Giới hạn
  • $2 \le N \le 100, 1 \le M \le 500, \sum cap_i \le 4000$.
  • Thời gian chạy: 3 giây.
Draft saved