Размерность максимальных потоков
Размерность максимальных потоков
Рассмотрим ациклический ориентированный граф G, с каждым ребром которого uv связана пропускная способность c(uv). Пусть G имеет две специальные вершины: исток s и сток t.
Потоком в G называется функция f : E -> R такая что следующие условия имеют место:
0 ≤ f(uv) ≤ c(uv) для всех ребер uv.
для всякой вершины u кроме s и t
Величина потока f обозначается как |f| - количество потока, исходящего из истока:
Поток называется максимальным если |f| наибольшее возможное среди всех потоков в G. Очевидно, что может существовать несколько максимальных потоков.
Потоки могут быть сложены поточечно или умножены на действительную константу, как и на любые другие функции. Зафиксируем некоторый максимальный поток f[max]
. Говорят, что множество потоков {f[1]
, f[2]
, ..., f[n]
} образуют базис максимальных потоков, если каждый максимальный поток можно представить в виде суммы
и никакое его подмножество не имеет этого свойства. Здесь a[i]
принадлежит R.
Размер этого множества - n - называется размерностью максимальных потоков графа.
По заданному графу G найдите размерность его максимальных потоков.
Входные данные
Первая строка содержит n и m - количество вершин и ребер в графе (1 ≤ n ≤ 10, 1 ≤ m ≤ 10). Каждая из следующих m строк содержит три целых числа и описывает ребра. Каждое ребро описывается исходящей вершиной, входящей вершиной и его пропускной способностью. Граф ациклический. Исток имеет номер 1, сток имеет номер n. Пропускные способности не превосходят 10^4
. Гарантируется, что существует путь из истока в сток.
Выходные данные
Выведите максимальную размерность максимальных потоков заданного графа.
Пример
2 1 1 2 1
0
4 5 1 2 2 1 3 2 3 2 1 2 4 2 3 4 1
1