Примеры сведения к задачам поиска потока — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример №1)
м (Пример №1)
Строка 15: Строка 15:
 
</includeonly>
 
</includeonly>
 
[[Файл:Monster.png|right|Пример поля]] [[Файл:MonsterSolution.png|right|Решение текущего примера]]
 
[[Файл:Monster.png|right|Пример поля]] [[Файл:MonsterSolution.png|right|Решение текущего примера]]
Во-первых, выбраться за пределы поля эквивалентно тому, что монстр может дойти до какой-либо крайней клетки. Во-вторых, заметим, что максимальное количество клеток, которые нужно закрасить, равно 4, т.к. можно закрасить клетку справа, слева, снизу и сверху от изначальной позиции монстра, чтобы он не смог никуда двигаться.
+
Сразу скажем, что выбраться за пределы поля эквивалентно тому, что монстр может дойти до какой-либо крайней клетки.
  
 
Покажем то, что минимальное количество клеток, которое нужно закрасить, равно максимальному количеству клеточно-непересекающихся путей из позиции монстра до крайних клеток поля. Очевидно, что ответ не больше, чем количество всех путей от монстра до крайних клеток. Сделаем ещё более строгое неравенство: ответ не больше, чем максимальное количество клеточно-непересекающихся путей, т.к. если мы возьмём какие-нибудь 2 пересекающихся пути и закрасим клетку в позиции, где они пересекаются, то мы блокируем путь монстру сразу по 2 этим путям. С другой стороны, если мы закрасим клетку на каком-то из путей, то у нас блокируется только этот путь, т.к. мы взяли клеточно-непересекающиеся пути. Значит, ответ не меньше, чем количество таких путей. В итоге получаем то, что и хотели доказать.
 
Покажем то, что минимальное количество клеток, которое нужно закрасить, равно максимальному количеству клеточно-непересекающихся путей из позиции монстра до крайних клеток поля. Очевидно, что ответ не больше, чем количество всех путей от монстра до крайних клеток. Сделаем ещё более строгое неравенство: ответ не больше, чем максимальное количество клеточно-непересекающихся путей, т.к. если мы возьмём какие-нибудь 2 пересекающихся пути и закрасим клетку в позиции, где они пересекаются, то мы блокируем путь монстру сразу по 2 этим путям. С другой стороны, если мы закрасим клетку на каком-то из путей, то у нас блокируется только этот путь, т.к. мы взяли клеточно-непересекающиеся пути. Значит, ответ не меньше, чем количество таких путей. В итоге получаем то, что и хотели доказать.

Версия 06:35, 25 декабря 2016

Пример №1

Задача:
Дано поле размером N * M, некоторые клетки поля закрашены. В одной из незакрашенных клеток поля стоит монстр, он умеет ходить только по незакрашенным клеткам (из текущей клетки он может пойти только в ту клетку, с которой имеет общую сторону). Какое минимальное количество клеток нужно закрасить, чтобы монстр не смог выбраться за пределы поля?


Пример поля
Решение текущего примера

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

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

Рассмотрим сеть, в которой вершинам будут соответствовать незакрашенные клетки поля, соседние незакрашенные клетки соединим ориентированными рёбрами с пропускной способностью 1. В качестве истока возьмём вершину, которой соответствует клетка монстра. Добавим в граф ещё одну вершину - сток, добавим рёбра из вершин, соответствующим крайним клеткам поля, в сток с пропускной способностью 1. Чтобы пути клеточно-непересекались, раздвоим каждую вершину графа на 2 вершины: в одну будут только входить рёбра, из другой - только выходить рёбра, и сами эти вершины соединим ребром с пропускной способностью 1.

Dublicate2.png

Используя алгоритм Диница, найдём максимальный поток в сети. Согласно теореме о декомпозиции, нахождение максимального потока эквивалентно тому, что мы нашли максимальное количество путей из истока в сток. Т.е. требуемый ответ на задачу равен максимальному потоку.