Максимальный поток минимальной стоимости
Максимальный поток минимальной стоимости
Задан ориентированный граф, каждое ребро которого обладает пропускной способностью и стоимостью.
Найдите максимальный поток минимальной стоимости из вершины с номером 1 в вершину с номером n.
Входные данные
Первая строка входного файла содержит n и m - количество вершин и количество ребер графа (2 ≤ n ≤ 100, 1 ≤ m ≤ 1000). Следующие m строк содержат по четыре целых числа числа: номера вершин, которые соединяет соответствующее ребро графа, его пропускную способность и его стоимость. Пропускные способности и стоимости не превосходят 105.
Выходные данные
В выходной файл выведите одно число - цену максимального потока минимальной стоимости из вершины с номером 1 в вершину с номером n. Ответ не превышает 263-1. Гарантируется, что в графе нет циклов отрицательной стоимости.
4 5 1 2 1 2 1 3 2 2 3 2 1 1 2 4 2 1 3 4 2 3
12