- 16.07.2017 16:14
- Информатика
- remove_red_eye 17191
- thumb_up 12
Ответы и объяснения 1
Дан граф с пропускной способностью и потоком для ребер из u в v. Необходимо найти максимальный поток из источника s в сток t. На каждом шаге алгоритма действуют те же условия, что и для всех потоков:. Поток из в не превосходит пропускной способности.. для всех узлов , кроме и . Поток не изменяется при прохождении через узел.Остаточная сеть — сеть с пропускной способностью и без потока.Вход Граф с пропускной способностью , источник и сток
Выход Максимальный поток из в
для всех ребер Пока есть путь из в в , такой что для всех ребер :Найти Для каждого ребра Путь может быть найден, например, поиском в ширину (алгоритм Эдмондса — Карпа) или поиском в глубину в .
- 17.07.2017 03:35
- thumb_up 15
Знаете ответ? Поделитесь им!
Есть сомнения?
Не нашли подходящего ответа на вопрос или ответ отсутствует? Воспользуйтесь поиском по сайту, чтобы найти все ответы на похожие вопросы в разделе Информатика.
Трудности с домашними заданиями? Не стесняйтесь попросить о помощи - смело задавайте вопросы!
Информатика — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.