Cho mạng luồng có hướng với sức chứa (capacity) trên mỗi cung, nguồn s và đích t. Luồng cực đại là lượng luồng lớn nhất có thể đẩy từ s tới t. Hãy tính giá trị luồng cực đại bằng thuật toán Ford-Fulkerson với tìm đường tăng BFS (Edmonds-Karp — xác định).
Dòng đầu n m. m dòng sau mỗi dòng u v c — cung có hướng từ u tới v sức chứa c. Dòng cuối s t.
1 <= n <= 200; 0 <= m <= 2000; 1 <= c <= 10^6; s != t.
Một số nguyên: giá trị luồng cực đại từ s tới t.
Ví dụ:
Đầu vào:
4 5
1 2 3
1 3 2
2 3 1
2 4 2
3 4 4
1 4
Đầu ra:
5
Giải thích:
Đang tải editor...