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