NGUỒN: Bài tập thầy Lê Minh Hoàng ôn Hải Phòng T10/2016
Cho mạng . Xác định luồng cực đại trên mạng.
Dữ liệu vào:
- Dòng đầu chứa số đỉnh , số cung của mạng, đỉnh phát , đỉnh thu ;
- dòng tiếp theo, dòng chứa thông tin về cung thứ gồm ba số nguyên dương tương ứng với một cung nối từ tới với sức chứa .
Dữ liệu ra:
- Dòng đầu ghi giá trị luồng cực đại;
- dòng tiếp, dòng ghi luồng trên cung thứ .
Ví dụ:
Dữ liệu vào:
6 8 1 6
5 6 6
4 6 6
3 5 1
3 4 3
2 5 3
2 4 6
1 3 5
1 2 5
Dữ liệu ra: