Изменения

Рассмотрим несколько задач, которые решаются путём сведения к задаче о поиске максимального потока в сети.

{{Задача

|definition = Дано поле размером <tex>N \times M</tex>, некоторые клетки поля закрашены. В одной из незакрашенных клеток поля стоит Минотавр, он умеет ходить только по незакрашенным клеткам (из текущей клетки он может пойти только в ту клетку, с которой имеет общую сторону). Какое минимальное количество клеток нужно закрасить, чтобы Минотавр не смог выбраться за пределы поля?

[[Файл:Monster.png|right|Пример поля]] [[Файл:MonsterSolution.png|right|Решение текущего примера]]

Сразу скажем, что выбраться за пределы поля эквивалентно тому, что Минотавр может дойти до какой-либо крайней клетки.

Покажем то, что минимальное количество клеток, которое нужно закрасить, равно максимальному количеству клеточно-непересекающихся путей из позиции Минотавра до крайних клеток поля. Очевидно, что ответ не больше, чем количество всех путей от Минотавра до крайних клеток. Сделаем ещё более строгое неравенство: ответ не больше, чем максимальное количество клеточно-непересекающихся путей, т.к. если взять какие-нибудь 2 пересекающихся пути и закрасить клетку в позиции, где они пересекаются, то блокируется выход за пределы поля сразу по 2 этим путям. С другой стороны, если закрасить клетку на каком-то из путей, то блокируется только этот путь, т.к. были взяты клеточно-непересекающиеся пути. Значит, ответ не меньше, чем количество таких путей. В итоге получаем то, что и хотели доказать.

Рассмотрим [[Определение сети, потока#flow_network|сеть]], в которой вершинам будут соответствовать незакрашенные клетки поля, соседние незакрашенные клетки соединим ориентированными рёбрами с пропускной способностью 1. В качестве истока возьмём вершину, которой соответствует клетка Минотавр. Добавим в граф ещё одну вершину — сток, добавим рёбра из вершин, соответствующим крайним клеткам поля, в сток с пропускной способностью 1. Чтобы пути не пересекались по клеткам, раздвоим каждую вершину графа на 2 вершины: в одну будут только входить рёбра, из другой — только выходить рёбра, и сами эти вершины соединим ребром с пропускной способностью 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(NM)</tex>. Второе замечание: ответ не превосходит 4, т.к. можно закрасить клетку слева, справа, сверху и снизу от позиции Минотавра и он не сможет никуда двигаться, поэтому <tex>|f|</tex> можно считать константой. Итоговое время работы <tex>O(NM)</tex>.