Vận chuyển tối ưu

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