Алгоритмы на графах

Для заданного графа с помощью алгоритма Форда-Фалкерсона найти максимальный поток.

Формат входных данных

В первой строке указан список вершин, разделённых пробелами. Первая указанная в списке вершина является источником, последняя – стоком.

Далее следуют строки, представляющие дуги графа (одна строка описывает одну дугу). Каждая строка содержит разделённые пробелами: имя начальной вершин, имя конечной вершины, пропускную способность дуги (число с 2 знаками после запятой).

В конце файла могут присутствовать пустые строки, в любом количестве.

Формат выходных данных

Первая строка содержит величину максимального потока, представленную в виде числа с 2 знаками после запятой.

Последующие строки описывают поток по дугам в таком же формате, как во входном файле, но вместо пропускной способности указан поток.