Mô tả và yêu cầu

AMAXFLOW
Cho mạng G có n đỉnh và m cạnh, đỉnh phát là 0, và đỉnh thu là n-1. Hãy tìm luồng
f* trong mạng sao cho giá trị val(f*) của luồng f* là lớn nhất.
Input: AMAXFLOW.INP
 Dòng 1: Ghi 2 số nguyên n, m cho biết số đỉnh và số cung trong mạng G.
 m dòng tiếp theo: Mỗi dòng ghi 3 số nguyên u, v, c cho biết cung nối từ u đến v có
trọng số là c
Output: AMAXFLOW.OUT
 Ghi một số nguyên dương cho biết giá trị luồng cực đại tìm được

Ví dụ

AMAXFLOW.INP            AMAXFLOW.OUT                                       Minh họa
6 9                     19
1 2 10
1 3 10
2 3 2
2 4 4
2 5 8
3 5 9
4 6 10
5 4 6
5 6 10
      Giải thích: Ta có luồng trên mạng trong test mẫu là:









      Ràng buộc: 0< n ≤ 500; 0< m ≤ 1000; 0 < c ≤ 109