Theo định lý max-flow min-cut, giá trị luồng cực đại từ s tới t bằng tổng sức chứa của lát cắt nhỏ nhất tách s khỏi t. Sau khi tính luồng cực đại, tập đỉnh phía nguồn là các đỉnh còn tới được từ s trong mạng thặng dư.
Hãy in giá trị lát cắt nhỏ nhất và tập đỉnh phía nguồn (tăng dần).
Dòng đầu n m. m dòng u v c (cung có hướng, sức chứa). Dòng cuối s t.
1 <= n <= 200; 0 <= m <= 2000; 1 <= c <= 10^6; s != t.
Dòng 1: giá trị lát cắt nhỏ nhất. Dòng 2: các đỉnh phía nguồn (kể cả s) theo thứ tự tăng dần, cách nhau bởi dấu cách.
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
1
Giải thích:
Đang tải editor...