Flow with Lower and Upper Bounds

Read Maximum flow before reading this article, and make sure you are familiar with the maximum-flow algorithm.

Overview

In essence, a flow network with lower and upper bounds assigns an upper bound $c(u,v)$ and a lower bound $b(u,v)$ to every edge. In other words, a feasible flow must satisfy $b(u,v) \leq f(u,v) \leq c(u,v)$. At the same time, flow conservation must hold at every vertex other than the source and sink.

Depending on the requirements of the problem, flow networks with lower and upper bounds can be used to solve different problems.

Feasible flow with lower and upper bounds and no source or sink

Given a flow network $G$ with no source or sink, determine whether there is a way to assign a flow to every edge so that all edge bounds and flow conservation at every vertex are satisfied.

Assume that every edge initially carries $b(u,v)$ units of flow, and call this the initial flow. In the new graph, also add an edge from $u$ to $v$ with capacity $c(u,v) - b(u,v)$. We will make adjustments in this new graph.

Because maximum flow requires the initial flow to satisfy flow conservation (maximum flow can be viewed as a lower-bounded maximum-flow problem with lower bound $0$), the constructed initial flow may fail to satisfy flow conservation. Suppose that, at some vertex, initial inflow minus initial outflow is $M$.

If $M=0$, flow is conserved and no auxiliary edge is needed.

If $M>0$, inflow is too large. Create an auxiliary source $S'$ and an auxiliary edge from $S'$ to this vertex with flow $M$.

If $M<0$, outflow is too large. Create an auxiliary sink $T'$ and an auxiliary edge from this vertex to $T'$ with flow $-M$.

If all auxiliary edges are saturated, the flow-conservation condition at this vertex can be satisfied; otherwise it cannot. (Only after the original graph is augmented with the auxiliary flow will flow conservation in the original graph hold.)

After constructing the graph, run maximum flow from $S'$ to $T'$. A feasible flow exists if and only if all edges leaving $S'$ are saturated.

Example

#include <iostream>
#include <queue>
using namespace std;
constexpr int MAXN = 3e4 + 10;
constexpr int INF = 1e9 + 10;
int n, m, s = 0, t;
int ecnt = 1, head[MAXN], dep[MAXN], now[MAXN], l[MAXN], d[MAXN], id[MAXN];

struct edge {
  int to, nxt, w;
} e[MAXN];

void add_edge(int u, int v, int w) {
  e[++ecnt] = {v, head[u], w};
  head[u] = ecnt;
}

void init() {
  for (int i = 0; i <= n + 1; i++) dep[i] = 0;
  for (int i = 0; i <= n + 1; i++) now[i] = head[i];
}

int bfs() {
  init();
  queue<int> q;
  q.push(s);
  dep[s] = 1;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = head[x]; i; i = e[i].nxt) {
      int v = e[i].to;
      if (dep[v] || !e[i].w) continue;
      dep[v] = dep[x] + 1;
      q.push(v);
    }
  }
  return dep[t];
}

int dfs(int x, int flow) {
  if (x == t) return flow;
  int ret = 0;
  for (int i = now[x]; i; i = e[i].nxt) {
    now[x] = i;
    int v = e[i].to;
    if (dep[v] != dep[x] + 1 || !e[i].w) continue;
    int w = dfs(v, min(flow - ret, e[i].w));
    e[i].w -= w;
    e[i ^ 1].w += w;
    ret += w;
    if (ret == flow) return ret;
  }
  return ret;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  s = 0, t = n + 1;
  for (int i = 1; i <= m; i++) {
    int u, v, r;
    cin >> u >> v >> l[i] >> r;
    add_edge(u, v, r - l[i]);
    add_edge(v, u, 0);
    id[i] = ecnt;
    d[v] += l[i];
    d[u] -= l[i];
  }
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    if (d[i] > 0) {
      add_edge(s, i, d[i]);
      add_edge(i, s, 0);
      sum += d[i];
    } else if (d[i] < 0) {
      add_edge(i, t, -d[i]);
      add_edge(t, i, 0);
    }
  }
  long long ans = 0;
  while (bfs()) ans += dfs(s, INF);
  if (ans < sum) {
    cout << "No\n";
    return 0;
  }
  cout << "Yes\n";
  for (int i = 1; i <= m; i++) cout << e[id[i]].w + l[i] << "\n";
  return 0;
}

Feasible flow with lower and upper bounds and a source and sink

Given a flow network $G$ with a source and sink, determine whether there is a way to assign a flow to every edge so that all edge bounds and flow conservation at every vertex other than the source and sink are satisfied.

Assume the source is $S$ and the sink is $T$.

Add an edge from $T$ to $S$ with upper bound $\infty$ and lower bound $0$. This reduces the problem to a feasible-flow problem with lower and upper bounds and no source or sink.

If a solution exists, the feasible-flow value from $S$ to $T$ equals the flow on the added edge from $T$ to $S$.

Maximum flow with lower and upper bounds and a source and sink

Given a flow network $G$ with a source and sink, determine whether there is a way to assign a flow to every edge so that all edge bounds and flow conservation at every vertex other than the source and sink are satisfied. If so, find the maximum possible flow value.

Find any feasible flow in the network. If none exists, stop immediately.

Otherwise, remove all auxiliary edges and consider the resulting residual network.

Run maximum flow from $S$ to $T$ once more in the residual network. The answer is the feasible-flow value plus this additional maximum-flow value.

Minimum flow with lower and upper bounds and a source and sink

Given a flow network $G$ with a source and sink, determine whether there is a way to assign a flow to every edge so that all edge bounds and flow conservation at every vertex other than the source and sink are satisfied. If so, find the minimum possible flow value.

Similarly, consider removing unnecessary flow from the residual network.

Find any feasible flow in the network. If none exists, stop immediately.

Otherwise, remove all auxiliary edges and consider the resulting residual network.

Run maximum flow from $T$ to $S$ once more in the residual network. The answer is the feasible-flow value minus this maximum-flow value.