Примеры сведения к задачам поиска потока
Рассмотрим несколько задач, которые решаются путём сведения к задаче о поиске максимального потока в сети.
Содержание
Пример №1. Лабиринт Минотавра
| Задача: |
| Дано поле размером , некоторые клетки поля закрашены. В одной из незакрашенных клеток поля стоит Минотавр, он умеет ходить только по незакрашенным клеткам (из текущей клетки он может пойти только в ту клетку, с которой имеет общую сторону). Какое минимальное количество клеток нужно закрасить, чтобы Минотавр не смог выбраться за пределы поля? |
Сразу скажем, что выбраться за пределы поля эквивалентно тому, что Минотавр может дойти до какой-либо крайней клетки.
Решение и доказательство корректности
| Теорема: |
Минимальное количество клеток, которое нужно закрасить, равно максимальному количеству клеточно-непересекающихся путей из позиции Минотавра до крайних клеток поля. |
| Доказательство: |
| Очевидно, что ответ не больше, чем количество всех путей от Минотавра до крайних клеток. Сделаем ещё более строгое неравенство: ответ не больше, чем максимальное количество клеточно-непересекающихся путей, т.к. если взять какие-нибудь пересекающихся пути и закрасить клетку в позиции, где они пересекаются, то блокируется выход за пределы поля сразу по этим путям. С другой стороны, если закрасить клетку на каком-то из путей, то блокируется только этот путь, т.к. были взяты клеточно-непересекающиеся пути. Значит, ответ не меньше, чем количество таких путей. |
Переход к сети
Рассмотрим сеть, в которой вершинам будут соответствовать незакрашенные клетки поля, соседние незакрашенные клетки соединим ориентированными рёбрами с пропускной способностью . В качестве истока возьмём вершину, которой соответствует клетка Минотавр. Добавим в граф ещё одну вершину — сток, добавим рёбра из вершин, соответствующим крайним клеткам поля, в сток с пропускной способностью . Чтобы пути не пересекались по клеткам, раздвоим каждую вершину графа на вершины: в одну будут только входить рёбра, из другой — только выходить рёбра, и сами эти вершины соединим ребром с пропускной способностью .
Используя алгоритм Форда-Фалкерсона, найдём максимальный поток в сети. Согласно теореме о декомпозиции, нахождение максимального потока эквивалентно тому, что мы нашли максимальное количество путей из истока в сток. Т.е. требуемый ответ на задачу равен максимальному потоку.
Оценка времени работы
Время работы алгоритма Форда-Фалкерсона . Первое замечание: (это следует из того, что из каждой вершины исходит не более рёбер), т.е. . Второе замечание: ответ не превосходит , т.к. можно закрасить клетку слева, справа, сверху и снизу от позиции Минотавра и он не сможет никуда двигаться, поэтому можно считать константой. Итоговое время работы .
Пример №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
