Network flow

Use maximum flow when units move from a source to a sink through directed edges with capacities. The answer is the largest feasible amount, not the cheapest path.

Model before algorithm

For every directed edge u → v:

• 0 ≤ flow(u,v) ≤ capacity(u,v);
• every internal vertex has equal incoming and outgoing flow;
• the objective is total flow leaving the source, equivalently entering the sink.

If a problem says “assign as many,” “route as much,” or “match the maximum number” under pairwise capacity constraints, try a flow model.

The residual graph

The residual graph records what can still change:

• a forward residual edge allows more flow to be sent;
• a reverse residual edge allows earlier flow to be cancelled and rerouted.

Reverse edges are not optional bookkeeping. Without them, an early valid choice can permanently block a better global solution.

flowchart LR
  accTitle: A residual edge supports both augmentation and cancellation
  accDescr: Sending delta units from u to v decreases the forward residual capacity and increases the reverse residual capacity, allowing later augmenting paths to cancel or reroute that flow.
  U["u"] -->|"forward residual = capacity - flow"| V["v"]
  V -.->|"reverse residual = flow"| U
  P["Augment by delta"] --> F["Forward residual<br/>subtract delta"]
  P --> R["Reverse residual<br/>add delta"]
  F --> Q["More capacity used"]
  R --> Z["Same flow can be cancelled<br/>and rerouted later"]

Think of the reverse edge as an undo budget. Every unit already sent forward creates one unit of permission to revise that choice.

Annotated Dinic blueprint

add_edge(u, v, capacity):
    add forward residual edge with capacity
    add reverse residual edge with zero capacity  # enables cancellation

while BFS can reach sink:
    level[v] = shortest residual-edge distance from source
    next_edge[v] = 0                              # avoid rescanning dead edges

    while pushed = DFS(source, infinity):
        total_flow += pushed

DFS(u, available):
    if u is sink: return available
    inspect only edges with level[v] = level[u] + 1
    push min(available, residual_capacity)
    subtract pushed flow from forward edge
    add pushed flow to reverse edge               # preserve residual invariant

Invariant: every residual update preserves capacity constraints and flow conservation.

Algorithm choice

Algorithm	Useful when	Typical bound
Edmonds–Karp	learning, small graphs, simplest correctness story	O(VE²)
Dinic	general interview and contest flow	O(V²E) general worst case
Hopcroft–Karp	the model is specifically unweighted bipartite matching	O(E√V)

Common reductions

• Bipartite matching: source → left side → right side → sink, all capacity one.
• Vertex capacity: split v into v_in → v_out with that capacity.
• Choose at most k: place capacity k on the controlling edge.
• Disjoint paths: capacity one on each edge or split vertices for vertex-disjoint paths.
• Minimum cut: after max flow, vertices still reachable in the residual graph form the source side of a minimum cut.

Failure checks

• Are capacities integral and within the numeric type?
• Did every added edge receive a paired reverse edge?
• Are parallel edges accumulated or represented separately?
• Is the graph directed as modeled, even when the story sounds symmetric?
• Does the reduction preserve “at most one” constraints on both sides?

Reference

• Princeton: Maximum Flow lecture
• Princeton: Ford–Fulkerson API and complexity

Tested Dinic template

PythonC++17C++11

@dataclass
class _FlowEdge:
    to: int
    reverse: int
    capacity: int


class Dinic:
    """Compute maximum flow with level graphs and blocking-flow DFS."""

    def __init__(self, vertex_count: int) -> None:
        if vertex_count < 0:
            raise ValueError("vertex_count must be nonnegative")
        self.graph: list[list[_FlowEdge]] = [[] for _ in range(vertex_count)]

    def add_edge(self, left: int, right: int, capacity: int) -> None:
        _validate_vertex(left, len(self.graph), "edge endpoint")
        _validate_vertex(right, len(self.graph), "edge endpoint")
        if capacity < 0:
            raise ValueError("capacity must be nonnegative")
        forward = _FlowEdge(right, len(self.graph[right]), capacity)
        backward = _FlowEdge(left, len(self.graph[left]), 0)
        self.graph[left].append(forward)
        self.graph[right].append(backward)

    def max_flow(self, source: int, sink: int) -> int:
        _validate_vertex(source, len(self.graph), "source")
        _validate_vertex(sink, len(self.graph), "sink")
        if source == sink:
            return 0
        total = 0
        while True:
            level = [-1] * len(self.graph)
            level[source] = 0
            queue = deque([source])
            while queue:
                node = queue.popleft()
                for edge in self.graph[node]:
                    if edge.capacity > 0 and level[edge.to] == -1:
                        level[edge.to] = level[node] + 1
                        queue.append(edge.to)
            if level[sink] == -1:
                return total

            next_edge = [0] * len(self.graph)

            def push(node: int, available: int) -> int:
                if node == sink:
                    return available
                while next_edge[node] < len(self.graph[node]):
                    edge = self.graph[node][next_edge[node]]
                    if edge.capacity > 0 and level[edge.to] == level[node] + 1:
                        sent = push(edge.to, min(available, edge.capacity))
                        if sent:
                            # Forward and reverse residual capacities change together.
                            edge.capacity -= sent
                            self.graph[edge.to][edge.reverse].capacity += sent
                            return sent
                    next_edge[node] += 1
                return 0

            while True:
                sent = push(source, 10**30)
                if not sent:
                    break
                total += sent

class Dinic {
 public:
  explicit Dinic(int vertex_count) {
    if (vertex_count < 0) {
      throw std::invalid_argument("vertex_count must be nonnegative");
    }
    graph_.resize(static_cast<std::size_t>(vertex_count));
  }

  void add_edge(int left, int right, long long capacity) {
    validate_vertex(left, graph_.size(), "edge endpoint");
    validate_vertex(right, graph_.size(), "edge endpoint");
    if (capacity < 0) {
      throw std::invalid_argument("capacity must be nonnegative");
    }
    const int left_reverse = static_cast<int>(graph_[right].size());
    const int right_reverse = static_cast<int>(graph_[left].size());
    graph_[left].push_back(Edge(right, left_reverse, capacity));
    graph_[right].push_back(Edge(left, right_reverse, 0));
  }

  long long max_flow(int source, int sink) {
    validate_vertex(source, graph_.size(), "source");
    validate_vertex(sink, graph_.size(), "sink");
    if (source == sink) {
      return 0;
    }
    long long total = 0;
    while (build_levels(source, sink)) {
      next_edge_.assign(graph_.size(), 0);
      while (true) {
        const long long sent =
            push(source, sink, std::numeric_limits<long long>::max());
        if (sent == 0) {
          break;
        }
        if (total > std::numeric_limits<long long>::max() - sent) {
          throw std::overflow_error("maximum flow overflow");
        }
        total += sent;
      }
    }
    return total;
  }

 private:
  struct Edge {
    Edge(int edge_to, int reverse_index, long long residual_capacity)
        : to(edge_to), reverse(reverse_index), capacity(residual_capacity) {}
    int to;
    int reverse;
    long long capacity;
  };

  bool build_levels(int source, int sink) {
    level_.assign(graph_.size(), -1);
    level_[source] = 0;
    std::queue<int> queue;
    queue.push(source);
    while (!queue.empty()) {
      const int node = queue.front();
      queue.pop();
      for (const auto& edge : graph_[node]) {
        if (edge.capacity > 0 && level_[edge.to] == -1) {
          level_[edge.to] = level_[node] + 1;
          queue.push(edge.to);
        }
      }
    }
    return level_[sink] != -1;
  }

  long long push(int node, int sink, long long available) {
    if (node == sink) {
      return available;
    }
    for (int& index = next_edge_[node];
         index < static_cast<int>(graph_[node].size()); ++index) {
      Edge& edge = graph_[node][index];
      if (edge.capacity == 0 || level_[edge.to] != level_[node] + 1) {
        continue;
      }
      const long long sent = push(edge.to, sink, std::min(available, edge.capacity));
      if (sent > 0) {
        // Forward and reverse residual capacities change together.
        edge.capacity -= sent;
        graph_[edge.to][edge.reverse].capacity += sent;
        return sent;
      }
    }
    return 0;
  }

  std::vector<std::vector<Edge>> graph_;
  std::vector<int> level_;
  std::vector<int> next_edge_;
};

class Dinic {
 public:
  explicit Dinic(int vertex_count) {
    if (vertex_count < 0) {
      throw std::invalid_argument("vertex_count must be nonnegative");
    }
    graph_.resize(static_cast<std::size_t>(vertex_count));
  }

  void add_edge(int left, int right, long long capacity) {
    validate_vertex(left, graph_.size(), "edge endpoint");
    validate_vertex(right, graph_.size(), "edge endpoint");
    if (capacity < 0) {
      throw std::invalid_argument("capacity must be nonnegative");
    }
    const int left_reverse = static_cast<int>(graph_[right].size());
    const int right_reverse = static_cast<int>(graph_[left].size());
    graph_[left].push_back(Edge(right, left_reverse, capacity));
    graph_[right].push_back(Edge(left, right_reverse, 0));
  }

  long long max_flow(int source, int sink) {
    validate_vertex(source, graph_.size(), "source");
    validate_vertex(sink, graph_.size(), "sink");
    if (source == sink) {
      return 0;
    }
    long long total = 0;
    while (build_levels(source, sink)) {
      next_edge_.assign(graph_.size(), 0);
      while (true) {
        const long long sent =
            push(source, sink, std::numeric_limits<long long>::max());
        if (sent == 0) {
          break;
        }
        if (total > std::numeric_limits<long long>::max() - sent) {
          throw std::overflow_error("maximum flow overflow");
        }
        total += sent;
      }
    }
    return total;
  }

 private:
  struct Edge {
    Edge(int edge_to, int reverse_index, long long residual_capacity)
        : to(edge_to), reverse(reverse_index), capacity(residual_capacity) {}
    int to;
    int reverse;
    long long capacity;
  };

  bool build_levels(int source, int sink) {
    level_.assign(graph_.size(), -1);
    level_[source] = 0;
    std::queue<int> queue;
    queue.push(source);
    while (!queue.empty()) {
      const int node = queue.front();
      queue.pop();
      for (const auto& edge : graph_[node]) {
        if (edge.capacity > 0 && level_[edge.to] == -1) {
          level_[edge.to] = level_[node] + 1;
          queue.push(edge.to);
        }
      }
    }
    return level_[sink] != -1;
  }

  long long push(int node, int sink, long long available) {
    if (node == sink) {
      return available;
    }
    for (int& index = next_edge_[node];
         index < static_cast<int>(graph_[node].size()); ++index) {
      Edge& edge = graph_[node][index];
      if (edge.capacity == 0 || level_[edge.to] != level_[node] + 1) {
        continue;
      }
      const long long sent = push(edge.to, sink, std::min(available, edge.capacity));
      if (sent > 0) {
        // Forward and reverse residual capacities change together.
        edge.capacity -= sent;
        graph_[edge.to][edge.reverse].capacity += sent;
        return sent;
      }
    }
    return 0;
  }

  std::vector<std::vector<Edge>> graph_;
  std::vector<int> level_;
  std::vector<int> next_edge_;
};

The implementation keeps reverse-edge indices beside every residual edge. Each blocking-flow phase scans only edges that advance one level.