50
правок
Изменения
м
→Пример №1
Покажем то, что минимальное количество клеток, которое нужно закрасить, равно максимальному количеству клеточно-непересекающихся путей из позиции монстра до крайних клеток поля. Очевидно, что ответ не больше, чем количество всех путей от монстра до крайних клеток. Сделаем ещё более строгое неравенство: ответ не больше, чем максимальное количество клеточно-непересекающихся путей, т.к. если взять какие-нибудь 2 пересекающихся пути и закрасить клетку в позиции, где они пересекаются, то блокируется выход за пределы поля сразу по 2 этим путям. С другой стороны, если закрасить клетку на каком-то из путей, то блокируется только этот путь, т.к. были взяты клеточно-непересекающиеся пути. Значит, ответ не меньше, чем количество таких путей. В итоге получаем то, что и хотели доказать.
Рассмотрим [[Определение сети, потока#flow_network|сеть]], в которой вершинам будут соответствовать незакрашенные клетки поля, соседние незакрашенные клетки соединим ориентированными рёбрами с пропускной способностью 1. В качестве истока возьмём вершину, которой соответствует клетка монстра. Добавим в граф ещё одну вершину - сток, добавим рёбра из вершин, соответствующим крайним клеткам поля, в сток с пропускной способностью 1. Чтобы пути клеточно-непересекалисьне пересекались по клеткам, раздвоим каждую вершину графа на 2 вершины: в одну будут только входить рёбра, из другой - только выходить рёбра, и сами эти вершины соединим ребром с пропускной способностью 1.
[[Файл:Dublicate2.png|center]]
Используя [[Схема алгоритма Диница|алгоритм Диница]], найдём максимальный поток в сети. Согласно [[Теорема о декомпозиции|теореме о декомпозиции]], нахождение максимального потока эквивалентно тому, что мы нашли максимальное количество путей из истока в сток. Т.е. требуемый ответ на задачу равен максимальному потоку.
