Vận chuyển tối ưu
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một đồ thị có hướng gồm $N$ đỉnh (đánh số từ $1$ đến $N$) và $M$ cung. Mỗi cung $(u, v)$ có sức chứa $cap$ và chi phí $cost$ cho mỗi đơn vị luồng đi qua.
Hãy tìm luồng cực đại từ đỉnh nguồn $1$ đến đỉnh đích $N$ sao cho tổng chi phí là nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($2 \le N \le 100, 1 \le M \le 1000$).
- $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 hai số nguyên: giá trị luồng cực đại và tổng chi phí nhỏ nhất tương ứng.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 3 2 1 3 2 4 2 3 1 1 2 4 2 5 3 4 3 1 |
5 28 |
Giới hạn
- $2 \le N \le 100, 1 \le M \le 1000$.
- Thời gian chạy: 2 giây.
Community Discussion