ALGO·III Алгоритмы Глава 25 из 65
Потоки и пары
Две смены одной задачи. Сначала штаб: секретный доклад RAND 1955 года, железные дороги на карте и поиск узкого места, которое ограничивает всю сеть. Потом день распределения: студенты, вузы и пары, которые никто не захочет разбить.
Алгоритмы
- 20 Поиск и сортировка
- 21 Разделяй и властвуй
- 22 Динамика
- 23 Жадные
- 24 Кратчайшие пути
- 25 Потоки и пары вы здесь
- 26 Случайность
- 27 Поиск в тексте
Опирается на: 24 · Навигатор
Что вы унесёте из главы
- находить максимальный поток и минимальный разрез сети и понимать, почему они равны
- сводить задачи о назначениях к потоку: кому какое место, если мест меньше, чем желающих
- строить устойчивые пары алгоритмом Гейла — Шепли и знать, какой стороне он выгоден
Навигатор из прошлой главы отвечал на вопрос одного пассажира: как доехать быстрее всего. Диспетчер спрашивает другое. По сети идут тысячи вагонов, у каждой дороги свой предел, и ему нужно знать, сколько всего проедет и что этому мешает. Эту главу мы проведём в двух ролях. В первой половине вы аналитик военного штаба 1955 года и ищете узкое место чужих железных дорог. Во второй — распорядитель дня распределения, который рассаживает студентов по вузам так, чтобы никому не захотелось сбежать. Задачи кажутся далёкими, но рассадка начнётся с того же потока, на котором кончится штаб.
Санта-Моника, 1955. Совершенно секретно
Харриса и Росса интересовал не столько сам поток грузов, сколько узкое место: набор участков, после выхода из строя которых сеть перестаёт работать. Это было предложение для авиации. Математики занимались этой сетью и раньше. В 1930 году А. Н. Толстой в сборнике Наркомата путей сообщения решал обратную задачу — как развезти грузы с наименьшим пробегом. Он заметил, что у лучшего плана нет «выгодных циклов»; той же идеей мы ловили арбитраж в прошлой главе. Толстой искал, как возить по этим дорогам дешевле, Харрис и Росс — где их перерезать.
Задачу аналитика можно решить и самому. Ниже — учебная карта по мотивам схемы Харриса и Росса: вершины — узлы, числа — сколько тысяч тонн в сутки пропускает линия в любую сторону. Числа выдуманы для урока. Задача: перекрыть линии так, чтобы из Москвы до Берлина нельзя было доехать, и чтобы сумма пропускных способностей перекрытых линий была как можно меньше. Эта сумма и есть «ширина» узкого места.
Если вы начали с самых толстых линий, то, скорее всего, потратили много и не отрезали ничего: у сети находились обходные пути. Об этом и писали Харрис и Росс. Специалисты того времени, по их словам, смотрели на сеть как на набор отдельных сквозных магистралей, и такой взгляд скрывал главное: даже если вывести из строя каждую магистраль, грузы могут пойти в обход. Перекрывать у самой Москвы тоже невыгодно, там слишком много выходов. Узкое место прячется посередине, и на глаз его найти трудно. Нужна теорема.
Сеть, поток и разрез
Отвлечёмся от карты и назовём вещи своими именами. Сеть — это ориентированный граф из главы 19, у которого выделены две вершины: исток $s$, откуда всё выезжает, и сток $t$, куда всё приезжает. У каждого ребра $u \to v$ есть пропускная способность $c(u, v)$ — сколько по нему можно провезти. Железную дорогу, по которой ходят в обе стороны, изображают двумя встречными рёбрами.
Поток — это план перевозок: по каждому ребру назначено, сколько везти, $f(u, v)$. План должен соблюдать два правила.
- Ребро не резиновое: $0 \le f(u, v) \le c(u, v)$.
- Груз не теряется и не появляется: в каждую вершину, кроме $s$ и $t$, въезжает столько же, сколько выезжает.
Величина потока $|f|$ — сколько выезжает из истока. По второму правилу столько же приезжает в сток: по дороге ничего не пропадает. Задача о максимальном потоке — найти поток наибольшей величины.
Теперь узкое место. Разделим вершины на две группы: $S$, где лежит исток, и $T$, где лежит сток. Это разрез, как в главе 23, только теперь у него есть берега: «наш» и «их». Ёмкость разреза $c(S, T)$ — сумма пропускных способностей рёбер, которые ведут из $S$ в $T$. Рёбра обратного направления, из $T$ в $S$, не считаются: по ним грузы едут назад, на наш берег.
Вот маленькая сеть, на которой мы будем учиться весь следующий раздел. Программа проверяет, что план перевозок соблюдает оба правила, и считает ёмкость нескольких разрезов.
Поток величины 5, разрезы ёмкостью 7, 9, 8 и 7: ни один разрез не меньше потока. Так будет всегда, и это первая, самая простая теорема главы.
Для любого потока $f$ и любого разреза $(S, T)$ выполнено $|f| \le c(S, T)$.
Сложим для всех вершин из $S$ разность «сколько выезжает минус сколько въезжает». У истока она равна $|f|$, у остальных вершин $S$ — нулю по второму правилу. Значит, сумма равна $|f|$. Теперь посмотрим на ту же сумму по рёбрам. Ребро с обоими концами в $S$ входит в неё дважды — с плюсом у начала и с минусом у конца — и сокращается. Остаются рёбра, пересекающие границу: из $S$ в $T$ с плюсом и из $T$ в $S$ с минусом. Получаем $|f| = \sum_{S \to T} f - \sum_{T \to S} f \le \sum_{S \to T} c = c(S, T)$, потому что первая сумма не больше пропускных способностей, а вторая не меньше нуля.
Всё, что выезжает из Москвы, рано или поздно пересекает любую линию фронта, и больше, чем вмещают пересекающие её дороги, через неё не пройдёт. Следствие очень полезное. Если вы предъявили поток и разрез одной величины, оба оптимальны: поток больше быть не может, потому что упирается в этот разрез, а разрез меньше быть не может, потому что через него уже идёт такой поток. Так вышло и у Харриса с Россом: их поток в 163 тысячи тонн и узкое место в 163 тысячи тонн проверяют друг друга, и никакой другой проверки не нужно.
Остаётся вопрос: всегда ли найдутся поток и разрез одной величины? Или бывает, что лучший поток строго меньше лучшего разреза? Чтобы ответить, надо научиться строить поток.
Затопление и его ловушка
Харрис и Росс считали поток методом «затопления», который их коллега по RAND Болдырефф описал летом 1955 года. Идея самая естественная, и в упрощённом виде она такая: найти любой путь от истока к стоку, где на всех рёбрах ещё есть место, и пустить по нему столько, сколько пропускает самое узкое ребро пути. Повторять, пока пути не кончатся. Болдырефф уверял, что правилам этой игры можно за несколько минут научить десятилетнего мальчика, и с этим не поспоришь. Беда в другом: ответ у метода не всегда верный.
Затопление остановилось на пяти. А разрез $\{s\}$ ёмкостью 7 подсказывает, что можно больше: из истока выходят рёбра на $4 + 3$. И правда, вот поток величины 7: по $s \to a \to t$ везём 3, по $s \to b \to t$ — 3, по $s \to a \to b \to t$ — ещё 1. Беда в первом ходе. Затопление пустило 3 по диагонали $a \to b$ и заняло ребро $b \to t$, которое нужно было грузам из $b$. Путей с местом больше нет, хотя поток не лучший. Жадный выбор, как в главе 23, завёл в тупик.
Отменить приказ: остаточная сеть
Спасает одна мысль: приказ можно отменить. Если по $a \to b$ уже едут 3 тонны, то «отправить 2 тонны из $b$ в $a$» не значит пустить поезд против движения. Это значит снять две тонны с диагонали: пусть они едут из $a$ прямо в $t$, а освободившееся место на $b \to t$ займут грузы, которые пришли в $b$ из истока. Назад не едет ни один вагон: меняется только план.
Запишем все возможности так. Остаточная сеть для потока $f$ — граф на тех же вершинах. Для каждого ребра $u \to v$ в ней есть прямое ребро с остатком $c(u, v) - f(u, v)$ — сколько ещё можно добавить, — и обратное ребро $v \to u$ с остатком $f(u, v)$ — сколько можно отменить. Рёбра с нулевым остатком не в счёт. Увеличивающий путь — путь из $s$ в $t$ по остаточной сети. Если он есть, по нему можно пустить столько, сколько пропускает его самое узкое ребро, и поток вырастет.
Код почти не меняется: при каждой отправке по ребру $u \to v$ мы уменьшаем остаток прямого ребра и на столько же увеличиваем остаток обратного.
Третий путь, $s \to b \to a \to t$, и есть отмена: по ребру $b \to a$ в исходной сети ничего не ездит, это обратное ребро для $a \to b$. Две тонны сняты с диагонали, ещё один путь — и поток дорос до 7, до ёмкости разреза $\{s\}$. Значит, это максимум.
В виджете ниже то же самое идёт по шагам. Сначала отмена выключена, и видно, где застревает затопление; потом включите её. Ещё можно сменить способ выбора пути и показать остаточную сеть.
Алгоритм, который повторяет «найди увеличивающий путь и пусти по нему поток», называют алгоритмом Форда — Фалкерсона. Какой путь брать, он не говорит; к этому вернёмся через раздел. Сначала докажем, что поток, для которого увеличивающих путей не осталось, наибольший.
Поток равен разрезу
Для потока $f$ в сети следующие три утверждения равносильны:
- $f$ — максимальный поток;
- в остаточной сети для $f$ нет увеличивающего пути;
- есть разрез $(S, T)$, для которого $|f| = c(S, T)$.
В частности, наибольшая величина потока равна наименьшей ёмкости разреза.
Из 1 следует 2. Если бы увеличивающий путь был, по нему можно было бы пустить ещё хоть сколько-то, и $f$ не был бы максимальным.
Из 2 следует 3. Пусть $S$ — вершины, до которых можно дойти из $s$ по остаточной сети, а $T$ — все остальные. Сток в $T$, иначе нашёлся бы увеличивающий путь, так что это разрез. Возьмём ребро $u \to v$ из $S$ в $T$. Если бы на нём оставалось место, прямое остаточное ребро довело бы нас до $v$, и $v$ попала бы в $S$. Значит, ребро загружено полностью: $f(u, v) = c(u, v)$. Возьмём ребро $v \to u$ из $T$ в $S$. Если бы по нему что-то ехало, обратное остаточное ребро $u \to v$ привело бы в $v$. Значит, $f(v, u) = 0$. Подставим в равенство из доказательства «поток не больше разреза»: $|f| = \sum_{S \to T} f - \sum_{T \to S} f = c(S, T) - 0$.
Из 3 следует 1. Любой поток не больше $c(S, T) = |f|$, значит, больше $f$ не бывает.
Доказательство заодно даёт рецепт поиска узкого места. Когда Форд — Фалкерсон остановился, обойдите остаточную сеть из истока — в глубину или в ширину, как в главе 19. Достижимые вершины — наш берег, остальные — чужой, а рёбра между ними — минимальный разрез. В виджете выше это закрашенные вершины.
Есть и ещё одно следствие, оно понадобится во второй половине главы. Если все пропускные способности — целые числа, алгоритм каждый раз пускает по пути целое число, ведь все остатки целые. Значит, найдётся максимальный поток, у которого на каждом ребре целое число. Это свойство называют целочисленностью потока.
Вы нашли в сети поток величины 12 и разрез ёмкости 15. Что можно сказать?
Поток 12 — нижняя оценка максимума, разрез 15 — верхняя. Пока они не сошлись, ответа нет. Остаточная сеть покажет, что делать: если в ней есть увеличивающий путь, поток можно увеличить; если нет, достижимые вершины дадут разрез ёмкости ровно 12.
Тысяча лишних шагов
Форд и Фалкерсон не сказали, какой путь выбирать. При целых пропускных способностях каждый шаг добавляет хотя бы единицу, так что алгоритм остановится не позже чем через $|f^*|$ шагов, где $f^*$ — максимальный поток. Но $|f^*|$ может быть огромным. Возьмём сеть из четырёх вершин: по краям рёбра на тысячу, посередине диагональ $a \to b$ с пропускной способностью 1. Вредный диспетчер каждый раз выбирает самый длинный путь — через диагональ, то туда, то обратно, — и прибавляет по единице.
Две тысячи увеличений против двух. Пропускные способности в миллиард сделали бы вредителя в миллион раз медленнее, а волне всё равно: ей хватит двух шагов. С иррациональными пропускными способностями всё ещё хуже: Форд и Фалкерсон сами построили пример, где неудачный выбор путей не останавливается никогда, а поток сходится к числу меньше максимума.
Лекарство — в функции shortest_path: искать увеличивающий путь обходом в ширину, то есть брать путь с наименьшим числом рёбер. Так устроен алгоритм Эдмондса — Карпа. Джек Эдмондс и Ричард Карп опубликовали его в 1972 году. А в Москве ещё в 1969 году Ефим Диниц, студент из группы Георгия Адельсон-Вельского (это его «АВ» в названии АВЛ-деревьев из главы 17), решал задачу, заданную на занятии, и придумал алгоритм быстрее, тоже на кратчайших путях; статья о нём вышла в «Докладах Академии наук СССР» в 1970 году. Число шагов у Эдмондса — Карпа зависит только от размеров сети, а не от чисел на рёбрах.
Если увеличивающий путь каждый раз выбирать кратчайшим по числу рёбер, увеличений будет не больше $V E$, а всё время работы — $O(V E^2)$, где $V$ — число вершин, $E$ — число рёбер.
Почему так
Пусть $d(v)$ — расстояние от истока до $v$ в остаточной сети, в рёбрах. Шаг 1: расстояния не уменьшаются. Увеличение по кратчайшему пути удаляет из остаточной сети рёбра, ставшие полными, и добавляет обратные. Каждое новое ребро $v \to u$ идёт против пути, по которому $d(v) = d(u) + 1$, то есть «назад», на уровень ближе к истоку. Рёбра, которые ведут назад или вбок, путь до вершины сократить не могут, поэтому все $d$ остаются прежними или растут.
Шаг 2: каждое ребро бывает узким нечасто. Назовём ребро $u \to v$ узким, если на нём достигается минимум пути; после увеличения оно исчезает из остаточной сети. В тот момент $d(v) = d(u) + 1$. Вернуться ребро может, только если по нему поедет поток назад, то есть если $v \to u$ окажется на кратчайшем пути: тогда $d'(u) = d'(v) + 1 \ge d(v) + 1 = d(u) + 2$. Каждый раз, когда ребро снова становится узким, расстояние до его начала выросло хотя бы на 2, а больше $V$ оно не бывает. Значит, каждое ребро бывает узким не больше $V/2$ раз.
Итог. В каждом увеличении есть узкое ребро; рёбер в остаточной сети не больше $2E$, и каждое бывает узким не больше $V/2$ раз — всего не больше $V E$ увеличений. Каждое ищется обходом в ширину за $O(E)$.
Для больших сетей есть алгоритмы быстрее. В 2022 году шесть авторов — Ли Чэнь, Расмус Кюнг, Ян Лю, Ричард Пэн, Максимилиан Пробст Гутенберг и Сушант Сачдева — показали, что максимальный поток при целых пропускных способностях можно найти почти за линейное время, $E^{1 + o(1)}$. Это теоретический рекорд; на практике чаще работают проверенные алгоритмы вроде алгоритма Диница.
Узкое место на карте штаба
Вернёмся к карте. Функция Эдмондса — Карпа лежит в модуле cs.flows вместе с учебной картой. Каждая линия карты — два встречных ребра. Найдём максимальный поток, а потом обойдём остаточную сеть из Москвы, как велит доказательство теоремы.
Четыре линии на 57 тысяч тонн: Вильнюс — Варшава, Минск — Брест, Гомель — Брест и Киев — Львов. Если вы перекрывали линии на карте сами, то нашли либо эти четыре, либо разрез подороже: следующий по дешевизне стоит 58. Перебирать все разрезы — путь тупиковый: у карты из 12 узлов их $2^{10} = 1024$, а у сети из 44 вершин, как у Харриса и Росса, — больше четырёх триллионов. Поток находит лучший за несколько обходов.
Минимальные разрезы применяют и в мирных задачах. На фотографии каждый пиксель — вершина, соседние пиксели связаны рёбрами, и чем ближе их цвета, тем больше пропускная способность ребра. Исток связан с пикселями, которые пользователь отметил как «объект», сток — с отмеченными как «фон». Минимальный разрез проходит там, где соседние пиксели сильнее всего различаются, — по контуру объекта. На этой идее построен, например, алгоритм выделения объектов GrabCut (2004). А мы закрываем штаб и переходим ко второй смене.
День распределения
Весной в зале сидят выпускники, у каждого список вузов, куда он готов пойти, а в каждом вузе по одному свободному месту. Нужно рассадить как можно больше людей. Это задача о паросочетании: выбрать набор пар «студент — вуз» так, чтобы каждый участвовал не больше чем в одной паре. Граф здесь особенный — двудольный: вершины делятся на две доли, студентов и вузы, и рёбра идут только между долями.
Жадная рассадка опять попадает в ловушку. Аня согласна на Политех или Универ, Боря — только на Политех. Если первой посадить Аню в Политех, Боря останется без места, хотя можно было посадить Аню в Универ. Это та же диагональ $a \to b$ из затопления, только с людьми, и выход тот же: превратить задачу в поток.
Добавим исток и сток. Из истока к каждому студенту проведём ребро с пропускной способностью 1: каждому — одно место. От студента к каждому вузу из его списка — ребро с пропускной способностью 1. От каждого вуза к стоку — ребро с пропускной способностью 1: в вузе одно место. По целочисленности найдётся максимальный поток, у которого на каждом ребре 0 или 1, а рёбра «студент — вуз» с единицей образуют паросочетание. Наоборот, любое паросочетание даёт поток той же величины. Значит, максимальный поток равен наибольшему паросочетанию.
Трое из четырёх, и лучше нельзя. Почему — объясняет минимальный разрез: Аня, Боря, Вера и Гоша вместе согласны только на три вуза — Политех, Универ и Мед. Четверым трёх мест не хватит, как ни рассаживай. Это частный случай теоремы Холла: паросочетание, в котором место есть у каждого студента, существует тогда и только тогда, когда любые $k$ студентов вместе называют хотя бы $k$ разных вузов. Её можно вывести из теоремы о разрезе.
Увеличивающий путь в такой сети начинается у студента без места, идёт к занятому вузу, по обратному ребру — к тому, кто там сидит, от него к другому вузу и так далее, пока не упрётся в свободный вуз. Это цепочка пересадок. Пусть Аня сидит в Политехе, Вера — в Универе, а Мед пока свободен; тогда Боря садится в Политех, Аня пересаживается в Универ, Вера — в Мед. В виджете «Увеличивающие пути» выше такая сеть есть в пункте «Места»: с включённой отменой там видно, как пересадка идёт по обратным рёбрам.
Максимум — ещё не мир
Поток рассадил как можно больше людей, но никого не спросил, кто чего хочет больше. Пусть Аня попала в Политех, а Боря в Универ. Аня мечтала об Универе, а Универ, будь его воля, взял бы Аню, а не Борю. Тогда утром Аня заберёт документы из Политеха, Универ откажет Боре, и распределение, которое так старательно считали, развалится. Такую пару — студент и вуз, которые оба предпочли бы друг друга тому, что им досталось, — называют блокирующей. Распределение без блокирующих пар — устойчивое.
Так и было в США с распределением в интернатуру. К концу 1940-х этот рынок лихорадило: больницы торопились занять лучших выпускников и требовали ответа сразу, выпускники отказывались в последний момент, когда приходило предложение получше. С 1952 года распределение взяла на себя общая служба — нынешняя Национальная программа подбора резидентов (NRMP). Через десять лет два математика, ничего о ней не зная, придумали тот же способ и объяснили, почему он работает.
Отложенное согласие
Способ Гейла и Шепли называют отложенным согласием. День распределения идёт по раундам.
- Каждый студент без места подаёт заявление в лучший вуз из своего списка, где ему ещё не отказывали.
- Каждый вуз смотрит на всех, кто к нему подал, вместе с тем, кого держит с прошлых раундов, оставляет лучшего — пока условно — и отказывает остальным.
- Отказанные снова свободны. Когда свободных не остаётся, условные согласия становятся окончательными.
Всё держится на слове «отложенное». Вуз не говорит «да» насовсем: он держит лучшего из тех, кто пришёл, но может передумать, если придёт кто-то ещё лучше. Студент же, получив отказ, больше в этот вуз не возвращается. Вот алгоритм на Python. Порядок, в котором свободные студенты подают заявления, не важен — скоро увидим почему, — так что здесь они подают по одному.
Словарь rank заведён ради скорости. Вуз постоянно сравнивает двух студентов, а метод index каждый раз проходил бы список с начала. Словарь из главы 8 отвечает за одно действие. Функция умеет и неполные списки: вуз, который кого-то не вписал, такому студенту откажет.
Предлагать можно и наоборот: пусть вузы зовут студентов, а студенты держат лучшее приглашение. Результат может получиться другим. Кому выгоднее быть стороной, которая подаёт заявления?
Выгоднее подавать. Кажется, что сильнее тот, кто выбирает, но он выбирает только из того, что к нему пришло, а подающий сам идёт сверху вниз по своему списку. Попробуйте в виджете ниже, а доказательство — сразу за ним.
Почему это работает
Пусть студентов и вузов поровну, по $n$, и каждый вписал в свой список всех с другой стороны. Докажем три вещи.
Алгоритм заканчивается не больше чем через $n^2$ заявлений, и в конце у каждого студента есть вуз.
Каждое заявление — это пара «студент, вуз», и в одну и ту же пару студент подаёт не больше одного раза: после отказа он идёт дальше по списку. Пар всего $n^2$. Теперь заметим, что вуз, к которому хоть раз подали, дальше всегда кого-то держит: он меняет студента только на лучшего. Если бы какой-то студент получил отказ от всех $n$ вузов, то к каждому вузу подавали, и каждый кого-то держит — то есть заняты $n$ мест другими студентами, а их всего $n - 1$. Противоречие.
В распределении, которое строит отложенное согласие, нет блокирующих пар.
Пусть студент $s$ попал в вуз $u'$, но предпочёл бы вуз $u$. Студенты идут по своим спискам сверху вниз, значит, в $u$ он подавал раньше, чем в $u'$, и получил отказ — сразу или позже, когда в $u$ пришёл кто-то лучше. С этого момента $u$ держал студентов не хуже того, ради кого отказал $s$: вуз меняет студента только на лучшего. Значит, свой итоговый студент для $u$ лучше, чем $s$, и пара $(s, u)$ не блокирующая.
Устойчивых распределений бывает несколько — в виджете их четыре. Какое из них выдаёт алгоритм? Назовём вуз достижимым для студента, если существует хоть одно устойчивое распределение, где они вместе.
Каждый студент получает лучший из достижимых для него вузов. В частности, результат не зависит от порядка заявлений, и все студенты одновременно получают лучшее, что возможно в устойчивом распределении.
Покажем, что студенту никогда не отказывает достижимый вуз. Тогда, идя по списку сверху вниз, он остановится не ниже лучшего достижимого, а выше остановиться не может, потому что итоговое распределение устойчиво и его вуз тоже достижим.
Пусть это не так, и рассмотрим первый за всю работу отказ достижимого вуза: вуз $u$ отказал студенту $s$, потому что держит или получил $s'$, которого ставит выше. Раз $u$ достижим для $s$, есть устойчивое распределение $M$, где $s$ учится в $u$; пусть $s'$ в нём учится в $u''$. До этого момента достижимые вузы никому не отказывали, значит, $s'$ не получал отказа от $u''$, а подал в $u$ — то есть ставит $u$ выше $u''$. Но и $u$ ставит $s'$ выше $s$. Выходит, $s'$ и $u$ в распределении $M$ — блокирующая пара, а $M$ устойчиво. Противоречие.
Есть и зеркальная половина: каждый вуз в этом распределении получает худшего из достижимых для него студентов. Доказательство в пару строк: если бы в каком-то устойчивом $M$ вуз $u$ получил студента хуже, чем $s$, которого он держит у нас, то $s$ в $M$ учится в вузе хуже $u$ (лучший достижимый для $s$ — это $u$), и $s$ с $u$ блокируют $M$. Теперь можно ответить на вопрос из опроса. Неважно, кто подаёт, только когда оба варианта дают одно и то же распределение; во всех остальных случаях выигрывает подающая сторона.
Когда подают студенты, сумма их номеров — 7, а у вузов — 12. Когда подают вузы — наоборот: 11 у студентов, 7 у вузов. Ни одному студенту от смены ролей не стало лучше.
Можно ли схитрить
Раз правила известны, участник может соврать о своих предпочтениях. Подающим это бесполезно: Лестер Дубинс и Дэвид Фридман в 1981 году и Элвин Рот в 1982-м доказали, что никакая ложь не улучшит подающему результат. Выбирающим хитрость иногда помогает. Вот три студента и три вуза; Политех «забывает» вписать в свой список Аню.
Получив отказ, Аня пошла в Универ и вытеснила Борю, Боря — в Мед и вытеснил Веру, а Вера пришла в Политех. Цепочка отказов принесла Политеху студента лучше. Но для такой хитрости надо знать чужие списки, а ошибка в расчёте может оставить вуз вовсе без студента. Вузам надёжнее с самого начала добиться, чтобы заявления подавали они.
Где это работает
Служба NRMP распределяет американских выпускников-медиков по больничным программам с 1952 года. В 1984 году Элвин Рот разобрал её правила и обнаружил, что они равносильны отложенному согласию, в котором подают больницы. Служба нашла устойчивые пары за десять лет до статьи Гейла и Шепли — и, как мы теперь знаем, выбрала вариант, выгодный больницам. Среди студентов это вызывало споры. В 1990-х службу перестроили по проекту Рота и Эллиотта Перансона, и с 1998 года заявления подают выпускники. Настоящая задача сложнее учебной: в больнице бывает много мест, а супружеские пары хотят попасть в один город. С парами устойчивого распределения может и вовсе не существовать, и алгоритм Рота — Перансона обходит это эвристиками.
С 2003 года отложенное согласие распределяет школьников по старшим школам Нью-Йорка. Тот же приём работает везде, где у обеих сторон есть предпочтения и места ограничены: студенты и общежития, аспиранты и научные руководители, кандидаты и компании на ярмарке вакансий. Проектировщику отсюда одно правило: подавать должна та сторона, чьи интересы вы хотите защитить, — ей не нужно хитрить.
Поток отвечает на вопрос «сколько», разрез — «что мешает», и они всегда равны. Паросочетание — это поток из единиц. Если у участников есть предпочтения, мало рассадить всех — нужно, чтобы никто не захотел сбежать, и отложенное согласие это гарантирует, причём в пользу подающей стороны.
Задачи
Четыре задачи: две из штаба, две со дня распределения. Сети в задачах — словари словарей, как в главе: graph[u][v] — пропускная способность ребра $u \to v$.
Напишите max_flow(graph, s, t) — величину максимального потока из s в t. Пропускные способности — неотрицательные целые числа, s != t. Вершина может встречаться только как конец ребра и не быть ключом словаря, а исток и сток — не встречаться в сети вовсе. Бывают встречные рёбра $u \to v$ и $v \to u$ одновременно. Переданную сеть менять нельзя. Сеть из 300 вершин и 4000 рёбер с числами до миллиона — быстрее трёх секунд.
Сначала соберите все вершины: и ключи, и концы рёбер. Для каждой заведите словарь остатков room[u]. Встречные рёбра складывайте, а не затирайте: room[u][v] = room[u].get(v, 0) + c, обратное — через setdefault(u, 0).
Путь ищите обходом в ширину с запоминанием, откуда пришли (came_from), как в главе 19. Узкое место пути — минимум остатков по нему; потом пройдите путь ещё раз и сдвиньте остатки: прямой — минус, обратный — плюс.
Это Эдмондс — Карп: число увеличений не зависит от величины чисел, поэтому тест «миллиард по краям» проходит за два шага. Обход останавливается, как только дошёл до стока, — на больших сетях это заметно экономит время.
Напишите min_cut(graph, s, t), которая возвращает список рёбер (u, v) минимального разреза: если их убрать, из s в t не пройти, а сумма их пропускных способностей наименьшая из возможных. Если разрезов минимальной ёмкости несколько, подойдёт любой. Если пути из s в t и так нет, верните пустой список. Сеть устроена как в прошлой задаче, менять её тоже нельзя; на 300 вершинах и 4000 рёбрах ответ нужен быстрее трёх секунд.
Вспомните доказательство теоремы о потоке и разрезе: после максимального потока достижимые из истока вершины образуют берег $S$, и все рёбра из $S$ в $T$ загружены полностью.
Возвращайте только рёбра из $S$ в $T$, причём рёбра исходной сети, а не остаточной. Рёбра из $T$ в $S$ в ёмкость разреза не входят.
Последний обход в ширину, который не дошёл до стока, уже нашёл берег $S$ — второй обход не нужен. Рёбра нулевой пропускной способности в ответ не берём: они ничего не стоят, но и ничего не перекрывают.
Напишите assign(wishes). На входе словарь: студент → список мест, куда он согласен. В каждом месте один человек. Верните словарь студент → место с наибольшим возможным числом пар; кто не поместился, в ответ не попадает. Если наибольших рассадок несколько, подойдёт любая. Списки бывают пустыми и с повторами; словарь пожеланий менять нельзя. Среди тестов есть цепочка из полутора тысяч пересадок и 2000 студентов, которых надо рассадить быстрее трёх секунд.
Можно собрать сеть, как в главе, и найти поток. А можно искать увеличивающий путь прямо в двудольном графе: от нового студента к местам из его списка; если место занято, к тому, кто его занимает, и дальше по его списку. Найденное свободное место завершает цепочку.
Ищите цепочку обходом в ширину и запоминайте для каждого места, кто хочет в него пересесть (came_from[место] = студент). Потом пройдите цепочку от свободного места назад: каждый пересаживается, освобождая место для предыдущего. Рекурсивный поиск в глубину на цепочке из 1500 пересадок упрётся в предел глубины рекурсии Python.
Это тот же Форд — Фалкерсон на сети из главы, только без явной сети: «пойти к тому, кто занимает место» — это шаг по обратному ребру. Кто однажды сел, уже не остаётся без места, его только пересаживают, поэтому студентов достаточно перебрать по одному разу. Время — $O(VE)$; есть и более быстрый алгоритм Хопкрофта — Карпа (1973), который ищет сразу много коротких цепочек.
Напишите stable_match(students, schools). Студентов и вузов поровну; students[s] — все вузы в порядке предпочтения студента $s$, schools[u] — все студенты в порядке предпочтения вуза $u$. Верните словарь студент → вуз: устойчивое распределение, лучшее для студентов. Входные списки менять нельзя. 600 студентов и 600 вузов со случайными списками, а также 1300 и 1300 с одинаковыми списками у всех — каждый раз быстрее трёх секунд.
Заведите для каждого студента номер следующего заявления, для каждого вуза — кого он сейчас держит, и список свободных студентов. Пока он не пуст: свободный подаёт в следующий вуз по своему списку.
Когда у всех одинаковые списки, заявлений будет около $n^2/2$ — для 1300 человек это 845 тысяч. Если каждый раз искать студента в списке вуза через index, к каждому сравнению добавятся сотни шагов. Заранее постройте словари rank[u][s].
По теореме из главы порядок, в котором свободные подают заявления, на результат не влияет, поэтому годится и стек, и очередь. Словари rank строятся за $O(n^2)$ — столько же, сколько занимают сами списки, — и после этого каждое заявление обрабатывается за $O(1)$.
Куда дальше
Мы искали узкое место между двумя городами. А если городов «своих» и «чужих» нет и нужно найти самое слабое место всей сети — наименьший набор линий, после которого она распадается на две части, всё равно какие? Можно перебрать все пары городов и для каждой найти поток. А можно поступить совсем странно: выбрать случайную линию, слить два её города в один, и повторять, пока не останутся два «сверхгорода». Линии между ними — разрез. Он бывает неудачным, но если повторить опыт достаточно раз, минимальный попадётся почти наверняка. Этот алгоритм Дэвид Каргер придумал в 1993 году, и он заметно проще потоковых. Иногда быстрее подбросить монетку, чем думать. Как случайность становится инструментом — в следующей главе.