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

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

Пример №1. Лабиринт Минотавра

Задача:

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

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

Решение и доказательство корректности

Теорема:

Минимальное количество клеток, которое нужно закрасить, равно максимальному количеству клеточно-непересекающихся путей из позиции Минотавра до крайних клеток поля.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Переход к сети

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

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

Оценка времени работы

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

Пример №2. Испорченный паркет.

Задача:

Дан паркет размером NxM, некоторые клетки которого испорчены, их необходимо закрыть новыми плитками. Плитки бывают размером 2х1 ценой А, и 1х1 ценой B. Плитки можно поворачивать, но нельзя разрезать. Какую минимальную сумму нужно потратить, что бы заложить испорченные плитки паркета. Новые плитки не должны перекрывать никакие другие плитки.

Решение

Сначала проверим, что 2*B>A. Если это условие не выполнено, то все выгодней замостить только плитками 1х1 и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой А. Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки 2х1 будет лежать на черной клетке, другой — на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая — черные. Ребра весом в 1 проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай f — величина найденного максимального потока между истоком и стоком, это и будет количество плиток 2х1. Ответом к задаче будет величина f*A+(K-f)*B, где K — общее количество испорченных клеток.

См.также

• Схема алгоритма Диница
• Алгоритм масштабирования потока

Источники информации

• The 2016 West Siberian Subregional Contest
• Источник: Харьковская зимняя школа по программированию, 2009, День 3