Luồng Cực Đại

Buổi 47 — Luồng cực đại (Dinic) Buổi 52 — Mock Contest Phase 2
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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
Draft saved