Недавно я встретил задачу 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$$$ потока. У нас, очевидно, скорее всего сломается сеть~--- в некоторые вершины будет приходить больше потока, чем уходить, а некоторые, наоборот, будут требовать поток. В некотором роде это ведь обычная задача на потоки~--- тоже есть две доли, одна поток выдаёт, вторая принимает, хотим все насытить. Чтобы к этому свести, сделаем такую модификацию сети. Введём ещё один исток $$$S'$$$ и сток $$$T'$$$, а каждое ребро $$$(u, v, l, r)$$$ заменим на привычные рёбра $$$(u, v, r - l)$$$, $$$(S', v, l)$$$ и $$$(u, T', l)$$$. Идея за этим следующая~--- в вершину $$$v$$$ пришло $$$l$$$ потока, который надо отдать, из вершины $$$r$$$ ушло $$$l$$$ потока, который надо вернуть.

Но какой смысл в смене истока и стока. Как поток будет идти из "перенасыщенных" вершин в "недонасыщенные"? Сейчас я сделаю последнее изменение сети~--- $$$(T, S, \inf)$$$~--- и объясню, зачем оно нужно. Рассмотрим какое-нибудь ребро $$$(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)$$$.

-1.png)

Синие рёбра — те, по которым пройдёт поток. То есть мы как бы начали поток $$$l$$$ через ребро, и вот этой сетью мы этот поток дополняем, чтобы он был из $$$S$$$ в $$$T$$$.

Таким образом нам надо найти максимальный поток из $$$S'$$$ в $$$T'$$$, чтобы "починить" сеть. Вернее сказать не максимальный, а поток определённой величины. Она равна сумме всех $$$l$$$. Но поскольку поток больше, чем эта величина, быть не может, нас интересует именно максимальный.

Отлично, мы починили сеть и пустили, по факту, минимально возможный поток. А теперь хотим сделать из него максимальный. Чтобы это сделать, можно просто запустить алгоритм поиска потока с оригинальными истоком и стоком, даже ничего прибавлять в конце не надо будет.