Mạng tuần hoàn có cận dưới

Buổi 48 — Min-Cost Max Flow
Points
85
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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:

  1. $low_e \le f(e) \le high_e$ với mọi cung $e$.
  2. 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 -1 nế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.
Draft saved