Изменения

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

== См.также ==