Недавно я встретил задачу [problem:2046D], которая напомнила мне про существование L-R потоков. Я их узнал очень давно, да и в тот момент задачи помимо "просто напиши L-R поток" нам не дали, так что я не запомнил алгоритм и мне пришлось узнать его заново, уже более детально. К сожалению блога на кфе, который бы всё понятно объяснил, не было, так что пришлось лазить по всяким другим ресурсам. Я нашёл их [тут](https://youkn0wwho.academy/topic-list/l_r_flow), примерно понял идею, потом пришлось смотреть реализацию, у меня к ней остались вопросы, я воспринимал немного как чёрный ящик. Но сегодня в 3 часа ночи мне пришло озарение и я всё понял. Чтобы тем 5 людям, которые прочитают мой блог, не пришлось его ждать, я хочу тут разъяснить моё понимание этого алгоритма и как его удобно писать.↵
↵
[cut]↵
↵
(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$. Но поскольку поток больше, чем эта величина, быть не может, нас интересует именно максимальный.↵
↵
Отлично, мы починили сеть и пустили, по факту, минимально возможный поток. А теперь хотим сделать из него максимальный. Чтобы это сделать, можно просто запустить алгоритм поиска потока с оригинальными истоком и стоком, даже ничего прибавлять в конце не надо будет. С реализацией можно ознакомиться ниже.↵
↵
<spoiler summary="Implementation of L-R flow">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <queue>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int inf = 1e9;↵
↵
template<int V>↵
struct MAX_FLOW {↵
struct edge {↵
int u, c, f;↵
};↵
↵
vector<int> g[V];↵
vector<edge> edges;↵
↵
void add_edge(int v, int u, int c) {↵
g[v].push_back(edges.size());↵
edges.push_back({u, c, 0});↵
g[u].push_back(edges.size());↵
edges.push_back({v, 0, 0});↵
}↵
↵
int d[V], ptr[V];↵
↵
bool bfs(int S, int T) {↵
fill(d, d + V, inf);↵
queue<int> q;↵
d[S] = 0;↵
q.push(S);↵
while (!q.empty()) {↵
int v = q.front();↵
q.pop();↵
for (int i : g[v]) {↵
const auto &[u, c, f] = edges[i];↵
if (c > f && d[u] > d[v] + 1) {↵
d[u] = d[v] + 1;↵
q.push(u);↵
}↵
}↵
}↵
return d[T] < inf;↵
}↵
↵
int dfs(int v, int T, int w = inf) {↵
if (v == T)↵
return w;↵
for (; ptr[v] < (int) g[v].size(); ptr[v]++) {↵
int i = g[v][ptr[v]];↵
const auto [u, c, f] = edges[i];↵
if (c > f && d[u] == d[v] + 1) {↵
int delta = dfs(u, T, min(w, c - f));↵
if (delta) {↵
edges[i].f += delta;↵
edges[i ^ 1].f -= delta;↵
return delta;↵
}↵
}↵
}↵
return 0;↵
}↵
↵
ll max_flow(int S, int T) {↵
ll flow = 0;↵
while (bfs(S, T)) {↵
fill(ptr, ptr + V, 0);↵
while (ll f = dfs(S, T))↵
flow += f;↵
}↵
return flow;↵
}↵
};↵
↵
const int N = 100;↵
↵
inline void solve() {↵
// super artificial problem just to show every small detail↵
// given a bipartite graph with n <= 100 vertices in each part↵
// and m edges between them with condition [l, r], meaning that flow though that edge must be in that range↵
// find max flow from first part to the second↵
// if every vertice from the first part must have at least 1 and at most a[i] flow↵
// and every vertice from the second part must have at least 1 and at most b[i] flow↵
int n, m; // number of vertices in each part, number of edges↵
cin >> n >> m;↵
MAX_FLOW<2 * N + 4> max_flow;↵
int S = n, T = n + 1, Sp = n + 2, Tp = n + 3; // sourse, sink, auxiliary sourse, auxiliary sink↵
vector<int> a(n), b(n); // capacities for first↵
for (int i = 0; i < n; i++)↵
cin >> a[i];↵
for (int i = 0; i < n; i++)↵
cin >> b[i];↵
ll suml = 0;↵
for (int i = 0; i < m; i++) {↵
int u, v, l, r;↵
cin >> u >> v >> l >> r;↵
u--;↵
v--;↵
suml += l;↵
max_flow.add_edge(u, v, r - l);↵
max_flow.add_edge(Sp, v, l);↵
max_flow.add_edge(u, Tp, l);↵
}↵
max_flow.add_edge(T, S, inf);↵
if (max_flow.max_flow(Sp, Tp) < suml) {↵
cout << -1 << '\n'; // L-R flow doesn't exist↵
return;↵
}↵
ll ans = max_flow.max_flow(S, T);↵
cout << ans << '\n';↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
И всё же, почему нам не надо ничего прибавлять, когда мы ищем максимальный поток из $S$ в $T$, у нас же сеть с пропускными способностями $r - l$, как мы прибавим всё то, что уже пустили? На этом этапе давайте поймём, какой поток мы пускаем, когда по всем рёбрам пускаем $l$. У каждой вершины появляется $overflow_v$ — сколько лишнего потока в ней есть, или сколько не хватает, в случае когда $overflow_v < 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 и радуйтесь жизни.
↵
[cut]↵
↵
(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$. Но поскольку поток больше, чем эта величина, быть не может, нас интересует именно максимальный.↵
↵
Отлично, мы починили сеть и пустили, по факту, минимально возможный поток. А теперь хотим сделать из него максимальный. Чтобы это сделать, можно просто запустить алгоритм поиска потока с оригинальными истоком и стоком, даже ничего прибавлять в конце не надо будет. С реализацией можно ознакомиться ниже.↵
↵
<spoiler summary="Implementation of L-R flow">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <queue>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int inf = 1e9;↵
↵
template<int V>↵
struct MAX_FLOW {↵
struct edge {↵
int u, c, f;↵
};↵
↵
vector<int> g[V];↵
vector<edge> edges;↵
↵
void add_edge(int v, int u, int c) {↵
g[v].push_back(edges.size());↵
edges.push_back({u, c, 0});↵
g[u].push_back(edges.size());↵
edges.push_back({v, 0, 0});↵
}↵
↵
int d[V], ptr[V];↵
↵
bool bfs(int S, int T) {↵
fill(d, d + V, inf);↵
queue<int> q;↵
d[S] = 0;↵
q.push(S);↵
while (!q.empty()) {↵
int v = q.front();↵
q.pop();↵
for (int i : g[v]) {↵
const auto &[u, c, f] = edges[i];↵
if (c > f && d[u] > d[v] + 1) {↵
d[u] = d[v] + 1;↵
q.push(u);↵
}↵
}↵
}↵
return d[T] < inf;↵
}↵
↵
int dfs(int v, int T, int w = inf) {↵
if (v == T)↵
return w;↵
for (; ptr[v] < (int) g[v].size(); ptr[v]++) {↵
int i = g[v][ptr[v]];↵
const auto [u, c, f] = edges[i];↵
if (c > f && d[u] == d[v] + 1) {↵
int delta = dfs(u, T, min(w, c - f));↵
if (delta) {↵
edges[i].f += delta;↵
edges[i ^ 1].f -= delta;↵
return delta;↵
}↵
}↵
}↵
return 0;↵
}↵
↵
ll max_flow(int S, int T) {↵
ll flow = 0;↵
while (bfs(S, T)) {↵
fill(ptr, ptr + V, 0);↵
while (ll f = dfs(S, T))↵
flow += f;↵
}↵
return flow;↵
}↵
};↵
↵
const int N = 100;↵
↵
inline void solve() {↵
// super artificial problem just to show every small detail↵
// given a bipartite graph with n <= 100 vertices in each part↵
// and m edges between them with condition [l, r], meaning that flow though that edge must be in that range↵
// find max flow from first part to the second↵
// if every vertice from the first part must have at least 1 and at most a[i] flow↵
// and every vertice from the second part must have at least 1 and at most b[i] flow↵
int n, m; // number of vertices in each part, number of edges↵
cin >> n >> m;↵
MAX_FLOW<2 * N + 4> max_flow;↵
int S = n, T = n + 1, Sp = n + 2, Tp = n + 3; // sourse, sink, auxiliary sourse, auxiliary sink↵
vector<int> a(n), b(n); // capacities for first↵
for (int i = 0; i < n; i++)↵
cin >> a[i];↵
for (int i = 0; i < n; i++)↵
cin >> b[i];↵
ll suml = 0;↵
for (int i = 0; i < m; i++) {↵
int u, v, l, r;↵
cin >> u >> v >> l >> r;↵
u--;↵
v--;↵
suml += l;↵
max_flow.add_edge(u, v, r - l);↵
max_flow.add_edge(Sp, v, l);↵
max_flow.add_edge(u, Tp, l);↵
}↵
max_flow.add_edge(T, S, inf);↵
if (max_flow.max_flow(Sp, Tp) < suml) {↵
cout << -1 << '\n'; // L-R flow doesn't exist↵
return;↵
}↵
ll ans = max_flow.max_flow(S, T);↵
cout << ans << '\n';↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
И всё же, почему нам не надо ничего прибавлять, когда мы ищем максимальный поток из $S$ в $T$, у нас же сеть с пропускными способностями $r - l$, как мы прибавим всё то, что уже пустили? На этом этапе давайте поймём, какой поток мы пускаем, когда по всем рёбрам пускаем $l$. У каждой вершины появляется $overflow_v$ — сколько лишнего потока в ней есть, или сколько не хватает, в случае когда $overflow_v < 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 и радуйтесь жизни.
