Məsələlər
Максимальный поток 2
Максимальный поток 2
Вам задан ориентированный граф G. Каждое ребро имеет некоторую пропускную способность. Найдите максимальный поток между вершинами 1 и n.
Giriş verilənləri
Первая строка входного файла содержит n и m - число вершин и рёбер в графе (2 ≤ n ≤ 500, 1 ≤ m ≤ 10000). Последующие строки описывают рёбра. Каждое ребро задается тремя числами: начальная вершина ребра, конечная вершина ребра и пропускная способность ребра. Пропускные способности не превосходят 10^9.
Çıxış verilənləri
Выведите величину максимального потока между вершинами 1 и n.
Nümunə
Giriş verilənləri #1
4 5 1 2 1 1 3 2 3 2 1 2 4 2 3 4 1
Çıxış verilənləri #1
3