Question

СПАСАЙТЕ КТО МОЖЕТ!!!! Пожалуйста помогите, нужен линейный алгоритм.

Answer 1

Дан граф  с пропускной способностью  и потоком  для ребер из u в v. Необходимо найти максимальный поток из источника s в сток t. На каждом шаге алгоритма действуют те же условия, что и для всех потоков:. Поток из  в  не превосходит пропускной способности.. для всех узлов , кроме  и . Поток не изменяется при прохождении через узел.Остаточная сеть  — сеть с пропускной способностью  и без потока.Вход Граф  с пропускной способностью , источник  и сток 
Выход Максимальный поток  из  в 
 для всех ребер Пока есть путь  из  в  в , такой что  для всех ребер :Найти Для каждого ребра Путь может быть найден, например, поиском в ширину (алгоритм Эдмондса — Карпа) или поиском в глубину в .