50
правок
Изменения
м
→Пример №1
Используя [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|алгоритм Форда-Фалкерсона]], найдём максимальный поток в сети. Согласно [[Теорема о декомпозиции|теореме о декомпозиции]], нахождение максимального потока эквивалентно тому, что мы нашли максимальное количество путей из истока в сток. Т.е. требуемый ответ на задачу равен максимальному потоку.
Время работы алгоритма Форда-Фалкерсона <tex>O(E|f|)</tex>. Заметим, что ответ не превосходит 4, т.к. можно закрасить клетку слева, справа, сверху и снизу от позиции монстра, и он не сможет никуда двигаться, поэтому <tex>|f|</tex> можно считать константой. Итоговое время работы <tex>O(E)</tex>.
