Недавно я встретил задачу 2046D - For the Emperor!, которая напомнила мне про существование L-R потоков. Я их узнал очень давно, да и в тот момент задачи помимо "просто напиши L-R поток" нам не дали, так что я не запомнил алгоритм и мне пришлось узнать его заново, уже более детально. К сожалению блога на кфе, который бы всё понятно объяснил, не было, так что пришлось лазить по всяким другим ресурсам. Я нашёл их тут, примерно понял идею, потом пришлось смотреть реализацию, у меня к ней остались вопросы, я воспринимал немного как чёрный ящик. Но сегодня в 3 часа ночи мне пришло озарение и я всё понял. Чтобы тем 5 людям, которые прочитают мой блог, не пришлось его ждать, я хочу тут разъяснить моё понимание этого алгоритма и как его удобно писать. (Prerequisites: задача о максимальном потоке, любой алгоритм для её решения)
Что такое вообще L-R поток?
В обычной версии максимального потока нам даются исток $$$S$$$, сток $$$T$$$, а также рёбра $$$(u, v, c)$$$, означающие, что из вершины $$$u$$$ в вершину $$$v$$$ есть направленное ребро с пропускной способностью $$$c$$$. По ребру может течь поток $$$0 \le f \le c$$$. В такой сети требуется найти максимальный поток. То есть нам дано верхнее ограничение на поток. В версии L-R на каждое ребро накладывается также и ограничение снизу, то есть теперь даются рёбра $$$(u, v, l, r)$$$ — теперь по ребру может течь поток $$$l \le f \le r$$$. Изначально может показаться, что это какое-то странное ограничение, но в некоторых задачах оно возникает вполне естественно. Давайте же научимся решать такую версию задачи о максимальном потоке. Сразу оговорюсь, что в задачах на L-R потоки сеть (почти) всегда ациклична, поскольку можно пустить поток по циклу, а не из $$$S$$$, и это как бы удовлетворяет ограничения, но смысла имеет мало. (по крайней мере задачи на это я не встречал, может быть такие и есть)
Для этого сведём её к обычной задаче о поиска потока. Давайте скажем, что по всем рёбрам мы сразу пустим $$$l$$$ потока. У нас, очевидно, скорее всего сломается сеть — в некоторые вершины будет приходить больше потока, чем уходить, а некоторые, наоборот, будут требовать поток. В некотором роде это ведь обычная задача на потоки — тоже есть две доли, одна поток выдаёт, вторая принимает, хотим все насытить. Чтобы к этому свести, сделаем такую модификацию сети. Введём ещё один исток $$$S'$$$ и сток $$$T'$$$, а каждое ребро $$$(u, v, l, r)$$$ заменим на привычные рёбра $$$(u, v, r - l)$$$, $$$(S', v, l)$$$ и $$$(u, T', l)$$$ (даже если один из концов пути — это $$$S$$$ или $$$T$$$). Идея за этим следующая — в вершину $$$v$$$ пришло $$$l$$$ потока, который надо отдать, из вершины $$$r$$$ ушло $$$l$$$ потока, который надо вернуть.
Но какой смысл в смене истока и стока. Как поток будет идти из "перенасыщенных" вершин в "недонасыщенные"? Сейчас я сделаю последнее изменение сети — $$$(T, S, \infty)$$$ — и объясню, зачем оно нужно. Рассмотрим какое-нибудь ребро $$$(u, v, l, r)$$$. Я заменил его на $$$(u, v, r - l)$$$, $$$(S', v, l)$$$, $$$(u, T', l)$$$, то есть я уже пустил $$$l$$$ потока по ребру, а также добавил требование его как-то вернуть. Но обычно мы ведь пускаем поток из $$$S$$$ в $$$T$$$, то есть это ребро должно быть на пути из $$$S$$$ в $$$T$$$. Попробуем пустить поток из $$$S'$$$ в $$$T'$$$. Пусть мы нашли путь $$$S', v, v_1, \ldots, v_k, T, S, v_{k+1}, \ldots, v_m, u, T'$$$ и пустили по нему $$$l$$$ потока. Тогда мы по сути дополнили путь из $$$S$$$ в $$$T$$$, проходящий через ребро $$$(u, v)$$$.
Синие рёбра — те, по которым пройдёт поток. То есть мы как бы начали поток $$$l$$$ через ребро, и вот этой сетью мы этот поток дополняем, чтобы он был из $$$S$$$ в $$$T$$$.
Таким образом нам надо найти максимальный поток из $$$S'$$$ в $$$T'$$$, чтобы "починить" сеть. Вернее сказать не максимальный, а поток определённой величины. Она равна сумме всех $$$l$$$. Но поскольку поток больше, чем эта величина, быть не может, нас интересует именно максимальный.
Отлично, мы починили сеть и пустили, по факту, минимально возможный поток. А теперь хотим сделать из него максимальный. Чтобы это сделать, можно просто запустить алгоритм поиска потока с оригинальными истоком и стоком, даже ничего прибавлять в конце не надо будет. С реализацией можно ознакомиться ниже.
И всё же, почему нам не надо ничего прибавлять, когда мы ищем максимальный поток из $$$S$$$ в $$$T$$$, у нас же сеть с пропускными способностями $$$r - l$$$, как мы прибавим всё то, что уже пустили? На этом этапе давайте поймём, какой поток мы пускаем, когда по всем рёбрам пускаем $$$l$$$. У каждой вершины появляется $$$overflow_v$$$ — сколько лишнего потока в ней есть, или сколько не хватает, в случае когда $$$overflow_v \lt 0$$$. Стоит вспомнить, что наша сеть ациклична, поэтому поток из $$$S'$$$ в $$$T'$$$ можно декомпозировать на следующие пути: $$$S', v, T'$$$ и те, что проходят через ребро $$$(T, S)$$$. Первый тип путей возникает из-за того, что в некоторую вершину может одновременно входить какой-то поток и выходить из неё же. Эти два ограничения друг друга уничтожают. В итоге у каждой вершины останется $$$|overflow_v|$$$ "перенасыщения" (или "недонасыщения"), которые уже должны будут пройти через ребро $$$(T, S)$$$. То есть через ребро $$$(T, S)$$$ мы пустим поток, равный сумме положительных $$$overflow_v$$$. Но как же он учтется при запуске max_flow(S, T)? А вот как, у нас есть обратное ребро из $$$S$$$ в $$$T$$$, и мы как бы отменим поток из $$$T$$$ в $$$S$$$, увеличив ответ как раз-таки на сумму положительных $$$overflow_v$$$, которую мы изначально пустили. Поэтому всё очень красиво сойдётся и не надо ничего держать в голове, просто вызывайте max_flow и радуйтесь жизни.
