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

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

Пример №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. Испорченный паркет.

Задача:

Дан паркет размером [math]N \times M[/math], некоторые клетки которого испорчены, их необходимо закрыть новыми плитками. Плитки бывают размером [math]2 \times 1[/math] ценой [math]A[/math], и [math]1 \times 1[/math] ценой [math]B[/math]. Плитки можно поворачивать, но нельзя разрезать. Какую минимальную сумму нужно потратить, чтобы заложить испорченные плитки паркета. Новые плитки не должны перекрывать никакие другие плитки.

Решение

Пример паркета

Пример раскраски

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

Доказательство корректности

Заметим следующее: мы ищем максимальное паросочетание в двудольном графе. Это означает, что белая вершина будет соединена не более чем с одной чёрной и наоборот – это именно то, что нам нужно, ведь соединяя чёрную клетку с белой, мы понимаем, что можем разместить здесь плитку размером [math]2 \times 1[/math] и она не будет ни с чем пересекаться. Теперь мы ищем максимальное число таких рёбер. Это всё происходит также, как и в сведении задачи поиска максимального паросочетания к задаче о нахождении максимального потока.

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

Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы [math]O(E|f|)[/math], где [math]|f|[/math] – величина найденного максимального потока. Заметим, что [math]|f| \leqslant \dfrac K 2[/math], где [math]K[/math] – общее число испорченных клеток. Также заметим, что [math]E \leqslant K \times 4[/math], т.к. [math]K[/math] рёбер исходят из истока и входят в сток и максимум [math]4[/math] ребра могут исходить из вершины в левой доле в правую. Из всего этого следует, что итоговое время работы будет [math]O(K^2)[/math]

Пример №3. Коллекционер монет.

Задача:

Есть [math]N[/math] коллекционеров и [math]M[/math] видов монет. Для вступления в клуб, необходимо иметь не меньше одной монеты каждого типа. Вы (у вас номер 1) можете меняться с коллекционерами имеющимися монетами. Любой коллекционер обменяет свою монету [math]a[/math] на вашу монету [math]b[/math], если у него больше одной монеты типа [math]a[/math] и нету ни одной монеты типа [math]b[/math]. Вы, в свою очередь, можете нарушать это правило. Нужно набрать как можно больше типов монет по известной ситуации у всех коллекционеров.

Решение

Жёлтые вершины – монеты разных типов, синие – коллекционеры. Красное ребро означает, что коллекционеру нужна монета этого типа, причём пропускная способнасть этого ребра равна 1, зелёное – что у него больше одной монеты данного типа

Построим сеть следующего вида: создадим для каждого типа монет по одной вершине, эти вершины будут соответствовать вашим монетам. Нужно собрать как можно больше уникальных монет, поэтому проведем ребро пропускной способности [math]1[/math] в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у вас. Для каждого члена клуба (кроме вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать не более [math]k-1[/math] монеты, которых у него [math]k[/math] [math](k \gt 1)[/math]. Естественно, член клуба отдает одну монету взамен одной полученной. Таким образом, в каждую такую вершину нужно провести ребро пропускной способности [math]1[/math] из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью [math]k_i - 1[/math] в вершину [math]i[/math], соответствующую монетам, которых у члена клуба больше одной. Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны вами.

Доказательство корректности

Как уже было сказано, построенная сеть отражает процессы обмена в клубе, пример можно посмотреть на картинке выше. Заметим следующее:

• из вершины каждого типа монет может выйти поток, величина которого [math]\leqslant 1 [/math]
• в вершины каждого типа монет может войти поток, величина которого не больше количества монет данного типа
• если коллекционеру нужна эта монета и мы решили дать её, то мы дадим максимум одну монету этого типа, т.к. пропускная способность красного ребра [math]= 1[/math].
• если в данную вершину пришёл поток данной величины, то мы должны отдать из этой вершины поток такой же величины. (Из определения потока)

Всё вышесказанное подтверждает то, что построенная сеть корректно отображает процессы обмена монетами между участниками.

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

Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы [math]O(E|f|)[/math], где [math]|f|[/math] – величина найденного максимального потока. Заметим, что [math]|f| \leqslant M[/math], где [math]M[/math] – количество типов монет. Также заметим, что [math]E = M \times 2 + E^*[/math], где [math]E^*[/math] – общее минимальное число монет, которые нужно получить все коллекционерам (кроме вас), чтобы вступить в клуб [math]+[/math] сумма типов монет, которых больше [math]1[/math], по всем коллекционерам. Из всего этого следует, что итоговое время работы будет [math]O(ME)[/math]

См.также

• Схема алгоритма Диница
• Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
• Алгоритм масштабирования потока

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

• The 2016 West Siberian Subregional Contest
• Зимняя школа по программированию, Харьков 2009
• Codeforces лекции Зимней Школы по Программированию