#556. HMAXFLOW – Luồng cực đại trên mạng

Cho mạng với là một đồ thị có hướng, không khuyên, có đỉnh và cung. Hai đỉnh phân biệt lần lượt là đỉnh phát và đỉnh thu. Khả năng thông qua của cung là . Từ chỉ có cung đi ra và từ chỉ có cung đi vào. Hãy tìm một luồng cực đại trêng mạng đã cho.

Dữ liệu vào:

• Dòng đầu chứa bốn số nguyên là số đỉnh và số cung của , đỉnh phát và đỉnh thu;
• dòng tiếp theo, mỗi dòng chứa ba số số cho biết một cạnh nối hai đỉnh và trong và khả năng thông qua tương ứng.

Dữ liệu ra:

• Dòng đầu ghi một số nguyên là giá trị của luồng;
• Những dong tiếp theo, mỗi dòng ghi ba số nguyên dương với là một cung và là giá trị của luồng trên cung đó (chỉ liệt kê những cung có ).

Ví dụ:

Dữ liệu vào:

6 8 1 6
1 2 5
1 3 5
2 4 6
2 5 3
3 4 3
3 5 1
4 6 6
5 6 6

Dữ liệu ra:

9
1 2 5
1 3 4
2 4 3
2 5 2
3 4 3
3 5 1
4 6 6
5 6 3

Giới hạn:

• .