Задачи
Максимальный поток A
Максимальный поток A
Дан неориентированный граф без петель и кратных ребер из $n$ вершин (вершины нумеруются от $1$ до $n$). Для каждого ребра известна его пропускная способность. Найдите величину максимального потока из вершины $1$ в вершину $n$. По каждому ребру поток может течь в любую сторону.
\InputFile
Два числа $n$ и $k~(2 \le n \le 100, 0 \le k \le n \cdot (n - 1) / 2)$ --- количество вершин и ребер в графе. Далее следуют $k$ строк по три числа в каждой --- $a, b, c~(1 \le a, b \le n, 1 \le c \le 10^9)$ --- номера вершин, соединенных ребром, и пропускная способность ребра.
\OutputFile
Выведите величину максимального потока из вершины $1$ в вершину $n$.
\includegraphics{https://static.eolymp.com/content/e3/e3080cfb1cfcec172da1c46589c25927008ff2dd.gif}
Входные данные #1
5 7 1 2 2 2 5 5 1 3 6 3 4 2 4 5 1 3 2 3 2 4 1
Выходные данные #1
6