Mạng Ống Dẫn Nước
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một mạng ống dẫn nước gồm N trạm (đánh số từ 1 đến N) và M đường ống một chiều. Mỗi đường ống nối từ trạm u đến trạm v có công suất tối đa c. Hãy tìm lưu lượng nước tối đa có thể bơm từ trạm nguồn 1 đến trạm đích N.
Dữ liệu vào
- Dòng đầu: hai số nguyên N và M (2 ≤ N ≤ 500, 0 ≤ M ≤ 5000).
- M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, c (1 ≤ u, v ≤ N, u ≠ v, 0 ≤ c ≤ 10^9).
Dữ liệu ra
- Một số nguyên duy nhất: lưu lượng cực đại từ đỉnh 1 đến đỉnh N.
Ví dụ
| Input | Output |
|---|---|
| 4 5\n1 2 10\n1 3 5\n2 3 15\n2 4 5\n3 4 10 | 15 |
Giới hạn
- 2 ≤ N ≤ 500
- 0 ≤ M ≤ 5000
- 0 ≤ c ≤ 10^9
Community Discussion