Recently I came across the problem 2046D - For the Emperor!, which reminded me of the existence of L-R flows. I first learned about them a long time ago, but at the time we weren't given any tasks beyond "just implement an L-R flow", so I didn't retain the algorithm and had to relearn it in more detail. Unfortunately, there wasn't a blog on Codeforces that explained everything clearly, so I had to dig through various other resources. I found them here, got a rough idea of the concept, and then had to look up an implementation. I still had some questions about it — it felt a bit like a black box. But at 3 a.m. today, something came to me and I finally understood it all. To save the 5 people who will read my blog from waiting for this insight, I want to explain my understanding of the algorithm here and how to implement it conveniently. (Prerequisites: max flow problem and any algorithm that solves it)

What's even an L-R flow?

In the standard version of the maximum flow problem, we're given a source $$$S$$$, a sink $$$T$$$, and edges of the form $$$(u, v, c)$$$, which represent a directed edge from vertex $$$u$$$ to vertex $$$v$$$ with capacity $$$c$$$. A flow along this edge must satisfy $$$0 \le f \le c$$$. The goal is to find the maximum flow through the network. In this version, we are only given an upper bound on the flow. In the L-R version, each edge also has a lower bound, so edges are given in the form $$$(u, v, l, r)$$$, meaning the flow along the edge must satisfy $$$l \le f \le r$$$. At first glance, this may seem like a strange constraint, but in some problems it arises quite naturally. Let's learn how to solve this version of the max flow problem.

Let me mention right away that in problems involving L-R flows, the network is (almost) always acyclic. This is because you could send flow around a cycle rather than from $$$S$$$, which might technically satisfy the constraints but is mostly meaningless. (At least, I haven't encountered any problems where cycles matter, though such problems might exist.)

To do this, we reduce it to the standard maximum flow problem. Let's say we initially send $$$l$$$ units of flow through every edge. Obviously, this will most likely break the network — some vertices will receive more flow than they send out, and others will demand more flow than they receive. In a way, this is just a standard flow problem — there are two sides, one supplies flow, the other consumes it, and we want to satisfy all demands. To reduce it to that, we'll make the following modification to the network. We introduce an additional source $$$S'$$$ and sink $$$T'$$$, and replace each edge $$$(u, v, l, r)$$$ with the familiar edges $$$(u, v, r - l)$$$, $$$(S', v, l)$$$, and $$$(u, T', l)$$$ (even if one of the endpoints is $$$S$$$ or $$$T$$$).

The idea behind this is as follows: vertex $$$v$$$ receives $$$l$$$ units of flow that it needs to send out, and vertex $$$u$$$ has $$$l$$$ units of flow going out that need to be compensated.

But what's the point of changing the source and sink? How will the flow move from "oversaturated" vertices to "undersaturated" ones? Now I'll make one final modification to the network — add the edge $$$(T, S, \infty)$$$ — and explain why it's needed. Let's look at some edge $$$(u, v, l, r)$$$. I replaced it with $$$(u, v, r — l)$$$, $$$(S', v, l)$$$, and $$$(u, T', l)$$$. That means I've already sent $$$l$$$ units of flow along the edge and added a requirement to somehow return it. But normally, we send flow from $$$S$$$ to $$$T$$$, so this edge should lie on a path from $$$S$$$ to $$$T$$$. Let's try sending flow from $$$S'$$$ to $$$T'$$$. Suppose we find a path $$$S', v, v_1, \ldots, v_k, T, S, v_{k+1}, \ldots, v_m, u, T'$$$ and send $$$l$$$ units of flow along it. Then, essentially, we've completed a path from $$$S$$$ to $$$T$$$ that goes through the edge $$$(u, v)$$$.

The blue edges are the ones through which the flow will pass. That is, we effectively started a flow of $$$l$$$ through the edge, and with this network, we're completing that flow so that it goes from $$$S$$$ to $$$T$$$.

Thus, we need to find a maximum flow from $$$S'$$$ to $$$T'$$$ in order to "fix" the network. More precisely, not a maximum flow, but a flow of a specific value. That value is equal to the sum of all $$$l$$$. But since the flow can't exceed this amount, we're essentially interested in the maximum flow.

Great, we've fixed the network and, in effect, sent the minimum possible flow. Now we want to turn it into a maximum flow. To do that, we can simply run a standard max flow algorithm using the original source and sink — there's no need to add anything at the end. You can find the implementation below.

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

And yet, why don't we need to add anything when we compute the maximum flow from $$$S$$$ to $$$T$$$? After all, our network has capacities $$$r - l$$$, so how do we account for the flow that we've already sent? At this point, let's try to understand what flow we're actually sending when we push $$$l$$$ through all the edges.

Each vertex gets an $$$overflow_v$$$ — how much extra flow it has, or how much it lacks if $$$overflow_v \lt 0$$$. It's important to recall that our network is acyclic, so the flow from $$$S'$$$ to $$$T'$$$ can be decomposed into the following kinds of paths: $$$S', v, T'$$$ and those that go through the edge $$$(T, S)$$$. The first type of path appears when some flow both enters and exits a vertex — these two constraints cancel each other out. As a result, each vertex ends up with $$$|overflow_v|$$$ of "oversaturation" (or "undersaturation"), which must then be routed through the edge $$$(T, S)$$$.

This means that the flow through the edge $$$(T, S)$$$ equals the sum of all positive $$$overflow_v$$$. But how is that accounted for when we run max_flow(S, T)?

Here's how: we have a reverse edge from $$$S$$$ to $$$T$$$, so we can "undo" the flow from $$$T$$$ to $$$S$$$, effectively increasing the result by exactly the amount of the positive $$$overflow_v$$$ that we initially pushed. So everything ties together nicely, and there's no need to keep anything extra in mind — just call max_flow and enjoy life.