Mạng tuần hoàn có cận dưới
Points
85
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một đồ thị có hướng gồm $N$ đỉnh và $M$ cung. Mỗi cung $(u, v)$ có cận dưới $low$, cận trên $high$ ($0 \le low \le high$) và chi phí $cost$ ($cost \ge 0$) cho mỗi đơn vị luồng.
Một luồng tuần hoàn hợp lệ là cách gán giá trị nguyên $f(e)$ cho mỗi cung sao cho:
- $low_e \le f(e) \le high_e$ với mọi cung $e$.
- Tại mọi đỉnh $v$, tổng luồng đi vào $v$ bằng tổng luồng đi ra khỏi $v$.
Hãy tìm tổng chi phí nhỏ nhất của một luồng tuần hoàn hợp lệ, hoặc in ra -1 nếu không tồn tại.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($2 \le N \le 200, 1 \le M \le 2000$).
- $M$ dòng tiếp theo, mỗi dòng chứa năm số nguyên $u, v, low, high, cost$ ($0 \le low \le high \le 10^4, 0 \le cost \le 10^4$).
Dữ liệu ra
- In ra tổng chi phí nhỏ nhất, hoặc
-1nếu không tồn tại.
Ví dụ
| Input | Output |
|---|---|
| 3 3 1 2 2 5 3 2 3 1 4 2 3 1 2 6 1 |
12 |
Giới hạn
- $2 \le N \le 200, 1 \le M \le 2000$.
- Thời gian chạy: 3 giây.
Community Discussion