Недавно я встретил задачу 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$$$. Но поскольку поток больше, чем эта величина, быть не может, нас интересует именно максимальный.

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

#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';
}

И всё же, почему нам не надо ничего прибавлять, когда мы ищем максимальный поток из $$$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 и радуйтесь жизни.