eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Максимальный поток в неориентированном графе

Максимальный поток в неориентированном графе

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Найдите величину максимального потока в заданном неориентированном графе.

Входные данные

Во входном файле заданы один или несколько тестов. Каждый тест начинается строкой, в которой содержится число n (2n100) — количество вершин графа. В следующей строке записаны три числа s, t и c — номер истока, номер стока, и количество ребер, соответственно. Далее следуют c строк, в каждой из которых содержатся три числа: номера соединенных ребром вершин и его пропускная способность — целое неотрицательное число, не превосходящее 1000. Между двумя парами вершин может быть более одного ребра, однако петли не допускаются.

Входной файл завершается фиктивным тестом, состоящим из одного числа 0, который обрабатывать не нужно.

Выходные данные

Для каждого из тестов выведите величину максимального потока.

Пример

Входные данные #1
4
1 4 5
1 2 20
1 3 10
2 3 5
2 4 10
3 4 20
0
Выходные данные #1
25