Cho một mạng luồng G có hướng, trên mỗi cung chứa một số nguyên thể hiện sức chứa của cung đó. Hãy tìm luồng cực đại trên mạng với đỉnh phát là ‘S’ và đỉnh thu là ‘T’. G có:

+ Chỉ có duy nhất một đỉnh phát ‘S’ và một đỉnh thu ‘T’

+ Ngoài đỉnh phát và đỉnh thu, các đỉnh còn lại có giá trị thuộc ‘A’ đến ‘O’

+ Không có chu trình trong G

+ Đường đi xuất phát từ 1 đỉnh bất kỳ đều kết thúc ở ‘T’

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên \(m\) cho biết số lượng cung

+ \(m\) dòng tiếp theo mỗi dòng ghi 3 giá trị \(V_{i}{\ V}_{j}\ c\) cho biết \(c\) là sức chứa của cung \((V_{i},V_{j})\)

Kết quả: Một số nguyên duy nhất là luồng cực đại trên G từ ‘S’ đến ‘T’

Giới hạn:

+ \(m \leq 50\)

+ \(1 < c \leq 50\)

Ví dụ: