eolymp
bolt
Try our new interface for solving problems
Məsələlər

Максимальный поток 2

Максимальный поток 2

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Вам задан ориентированный граф G. Каждое ребро имеет некоторую пропускную способность. Найдите максимальный поток между вершинами 1 и n.

Giriş verilənləri

Первая строка входного файла содержит n и m - число вершин и рёбер в графе (2n500, 1m10000). Последующие строки описывают рёбра. Каждое ребро задается тремя числами: начальная вершина ребра, конечная вершина ребра и пропускная способность ребра. Пропускные способности не превосходят 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