Luồng Cực Đại
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho mạng lưới gồm N đỉnh và M cạnh có hướng. Mỗi cạnh có sức chứa c. Hãy tìm luồng cực đại từ đỉnh nguồn 1 đến đỉnh đích N.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên N M (2 ≤ N ≤ 500, 1 ≤ 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, 1 ≤ c ≤ 10^9) mô tả cạnh có hướng từ u đến v với sức chứa c.
Dữ liệu ra
In ra luồng cực đại.
Ví dụ
| Input | Output |
|---|---|
| 4 5\n1 2 10\n1 3 10\n2 3 2\n2 4 8\n3 4 10 | 18 |
Giới hạn
- 2 ≤ N ≤ 500
- 1 ≤ M ≤ 5000
- 1 ≤ c ≤ 10^9
Community Discussion