Max Flow

For equality, the first inequality requires all edges in $\{(u, v) \mid u \in T, v \in S\}$ to carry zero flow, and the second requires all edges in $\{(u, v) \mid u \in S, v \in T\}$ to be saturated. The original lemma follows.

Suppose that after one augmentation we obtain a flow $f$ such that no augmenting path exists in $G_f$, that is, in $G_f$ there is no path from $s$ to $t$. Let the vertices reachable from $s$ form the set $S$, and let $T = V \setminus S$.

Clearly, $\{S, T\}$ is a cut of $G_f$, and $||S, T|| = \sum_{u \in S} \sum_{v \in T} c_f(u, v) = 0$. Since residual capacities are nonnegative, this also means that for any $u \in S, v \in T, (u, v) \in E_f$, we have $c_f(u, v) = 0$. We now discuss these edges in two cases, according to whether they exist in the original graph or are reverse edges:

• $(u, v) \in E$: in this case, $c_f(u, v) = c(u, v) - f(u, v) = 0$, so $c(u, v) = f(u, v)$; all edges in $\{(u, v) \mid u \in S, v \in T\}$ are saturated;
• $(v, u) \in E$: in this case, $c_f(u, v) = c(u, v) - f(u, v) = 0 - f(u, v) = f(v, u) = 0$; all edges in $\{(v, u) \mid u \in S, v \in T\}$ carry zero flow.

Therefore, after augmentation stops, the flow $f$ satisfies the equality conditions above. By the size relation stated in the lemma, $f$ is naturally a maximum flow of $G$, and $\{S, T\}$ is a minimum cut of $G$.

First, we introduce a lemma—the shortest-path nondecreasing lemma. Let $d_f(u)$ denote the distance in $G_f$ from vertex $u$ to the source $s$ (that is, the shortest-path length; the same convention applies below). For one augmentation, let $f$ and $f'$ denote the flow before and after augmentation, respectively. We claim that for every vertex $u$, augmentation always gives $d_{f'}(u) \geq d_f(u)$. We prove this lemma shortly.

Call an edge with minimum residual capacity on an augmenting path a saturated edge (if several edges attain the minimum, choose any one). If a directed edge $(u, v)$ is selected as the saturated edge, augmentation empties its residual capacity, causing the saturated edge to disappear, while flow cancellation adds its reverse edge (if the reverse edge did not previously exist), namely $(u, v) \not \in E_{f'}$ and $(v, u) \in E_{f'}$. This analysis shows that for an undirected edge $(u, v)$, when augmenting in $G_f$ along $(u, v)$, $d_f(u) + 1 = d_f(v)$. The residual network then becomes $G_{f'}$. In $G_{f'}$, augment along $(v, u)$, $d_{f'}(v) + 1 = d_{f'}(u)$. By the shortest-path nondecreasing lemma, $d_{f'}(v) \geq d_f(v)$. Combining these equations gives $d_{f'}(u) \geq d_{f}(u) + 2$. In other words, if directed edge $(u, v)$ is selected as a saturated edge, then compared with the previous time it was selected, the distance from $u$ to $s$ increases by at least $2$.

The distance from $s$ to any vertex cannot exceed $|V|$. Together with the property above, this shows that each edge is selected as a saturated edge $O(|V|)$ times. Multiplying by the number of edges gives the upper bound $O(|V||E|)$ on the total number of augmentations.

We now prove the shortest-path nondecreasing lemma, namely $d_{f'}(u) \geq d_f(u)$. The proof is not difficult, but may be somewhat circuitous, so readers may wish to pause and think carefully.

constexpr int MAXN = 250;
constexpr int INF = 0x3f3f3f3f;

struct Edge {
  int from, to, cap, flow;

  Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

struct EK {
  int n, m;             // n: number of vertices, m: number of edges
  vector<Edge> edges;   // edges: collection of all edges
  vector<int> G[MAXN];  // G: indices in edges of all edges starting at vertex x
  int a[MAXN], p[MAXN];  // a: maximum flow assigned to x by the edge that first reaches x during BFS
                         // p: edge that first reaches x during BFS

  void init(int n) {
    for (int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }

  void AddEdge(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }

  int Maxflow(int s, int t) {
    int flow = 0;
    for (;;) {
      memset(a, 0, sizeof(a));
      queue<int> Q;
      Q.push(s);
      a[s] = INF;
      while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        for (int i = 0; i < G[x].size(); i++) {  // Traverse edges starting at x
          Edge& e = edges[G[x][i]];
          if (!a[e.to] && e.cap > e.flow) {
            p[e.to] = G[x][i];  // G[x][i] is the edge that first reaches e.to
            a[e.to] =
                min(a[x], e.cap - e.flow);  // Assign the flow of the edge that first reaches e.to
            Q.push(e.to);
          }
        }
        if (a[t]) break;  // If the sink has received flow, exit BFS
      }
      if (!a[t])
        break;  // If the sink received no flow, the source and sink are disconnected
      for (int u = t; u != s;
           u = edges[p[u]].from) {  // Trace the s -> t path found by BFS through u
        edges[p[u]].flow += a[t];      // Increase the flow on the path edge
        edges[p[u] ^ 1].flow -= a[t];  // Decrease the flow on the reverse edge
      }
      flow += a[t];
    }
    return flow;
  }
};

Multi-path augmentation is a constant-factor optimization of the Dinic algorithm. If we find a path from $s$ to $t$ in the level graph and call it $p$, we need not necessarily start from $s$ again to find the next augmenting path; instead, we may start from the last position on $p$ that still has residual capacity and search for a branch for another augmentation. Because this is consistent with the backtracking form, the optimization arises naturally in the DFS implementation.

Consider every augmenting path in the blocking flow $f_b$. Each is obtained on $G_L$ by repeatedly following the current arc, and the number of jumps along each augmenting path is at most $|V|$.

Each time an augmenting path is found, one saturated edge disappears (its residual capacity becomes zero). For every augmenting path in $f_b$, let $E_1$ be the set of saturated edges whose residual capacities it clears. Because of the layering property of $G_L$, after a saturated edge disappears, its reverse edge cannot be traversed by another augmenting path in the same augmentation phase. Therefore, $E_1$ is a subset of $E_L$.

In addition, for cases where following current arcs is blocked at some position and therefore does not successfully produce an augmenting path, let $E_2$ be the set of final edges on these incomplete paths. Members of $E_2$ are not saturated, so $E_1$ and $E_2$ are disjoint, and $E_1 \cup E_2$ is still a subset of $E_L$.

Every member of $E_1 \cup E_2$ is involved in at most $|V|$ jumps (and some jumps are counted repeatedly after multi-path augmentation optimization). Therefore, the total number of jumps in the DFS process is at most $|V||E_L|$.

We introduce a concept from preflow-push algorithms (another class of maximum-flow algorithms)—height labels. To state the proof more conveniently with height labels, let $d_f(u)$ denote the distance in $G_f$ from vertex $u$ to the sink $t$, and build layers from the sink rather than the source (there is no essential difference). For one augmentation phase, let $f$ and $f'$ be the flows before and after augmentation. After finding and adding the blocking flow in this phase, let the level graph change from $G_L = (V, E_L)$ to $G'_{L} = (V, E'_L)$.

Temporarily, and somewhat informally, define a height label as follows: on a network $G = (V, E)$, let $h$ be a function from $V$ to the integers $N$; $h$ is a valid height labeling on $G$ if and only if $h(u) \leq h(v) + 1$ holds for every $(u, v) \in E$.

Consider $E_{f'}$, and for each member $(u, v)$, we find that $(u, v) \in E_{f'}$ for one of two reasons:

• $(u, v) \in E_f$, and its residual capacity was not exhausted during this augmentation phase. By the definition of shortest paths, $d_f(u) \leq d_f(v) + 1$;
• $(u, v) \not \in E_f$, but the blocking flow traversed $(v, u)$ during this augmentation phase and generated the reverse edge through cancellation. By the definition of the level graph and blocking flow, $d_f(u) + 1 = d_f(v)$.

These observations show that $d_f$ is a valid height labeling on $G_{f'}$, and of course also on $G_{f'}$ and its subgraph $G'_L$, namely the level graph $G'_L$.

Now consider an augmenting path $p = (s, \dots, u, v, \dots, t)$. Starting from the empty path, consider adding vertices one at a time in reverse order along $p$, from $t$ to $s$. Suppose $v$ has already been added and $u$ is being added. After adding $u$, by the definition of the level graph, the value of $d_{f'}(u)$ is greater than $d_{f'}(v)$ by $1$. Meanwhile, because $d_f$ is a height labeling on $G'_L$, $d_f(u)$ may be greater than $d_f(v)$ by $1$, equal to it, or smaller. Therefore, after adding the entire path, we obtain $d_{f'}(s) \geq d_f(s)$, with equality if and only if $d_f(u) = d_f(v) + 1$ for every $(u, v) \in p$. If equality does not hold, then $d_{f'}(s) > d_f(s)$—the desired conclusion that the number of layers strictly increases during augmentation. We now prove that equality cannot hold.

Suppose for a contradiction that $d_{f'}(s) = d_f(s)$. We claim that in $G'_L$, the path $p$ contains at least one edge $(u, v)$; this edge $(u, v)$ does not exist in $G_L$. If no such edge existed, then because $d_f(s) = d_{f'}(s)$, the definitions of the level graph and blocking flow would imply that augmentation in $G_L$ was not complete. To avoid this contradiction, our claim must be true.

Let $(u, v)$ be an edge satisfying the claim. There are only two possible reasons:

• $(u, v) \in E_f$, but $d_f(u) \leq d_f(v) + 1$ is strict, so by the definition of the level graph, $(u, v) \not \in E_L$ and is added to $E'_L$ when the graph is re-layered after augmentation;
• $(u, v) \not \in E_f$, which means that edge $(u, v)$ was created when the blocking flow traversed $(v, u)$ during the current augmentation phase and generated a reverse edge through cancellation, that is, $d_f(u) = d_f(v) - 1$.

In either case, we obtain $d_f(u) \neq d_f(v) + 1$. Thus the necessary and sufficient condition for equality in $d_{f'}(s) \geq d_f(s)$ cannot be satisfied, contradicting the assumption $d_{f'}(s) = d_f(s)$. The proposition follows.

This is because every augmentation saturates and removes all edges on the augmenting path, so each edge can be augmented only once in a single augmentation phase.

Build layers centered at the source $s$, let $d_f(u)$ denote the distance in $G_f$ from vertex $u$ to the source $s$. In addition, define the set $\left\{u \mid u \in V, d_f(u) = k \right\}$ as the layer with index $k$, denoted $D_k$, and let $S_k = \cup_{i \leq k} D_i$.

Suppose we have performed $|E|^{\frac{1}{2}}$ augmentation phases. By the pigeonhole principle, there is at least one $k$ such that the edge set $\left\{ (u, v) \mid u \in D_k, v \in D_{k+1}, (u, v) \in E_f \right\}$ has size at most $\frac {|E|} {|E|^{\frac{1}{2}}} \approx |E|^{\frac{1}{2}}$. Clearly, $\{S_k, V - S_k\}$ is a cut in $G_f$ separating $s$ and $t$, and its cut capacity is at most $|E|^{\frac{1}{2}}$. By the max-flow min-cut theorem, the maximum flow in $G_f$ is at most $|E|^{\frac{1}{2}}$, meaning that in $G_f$ at most $|E|^{\frac{1}{2}}$ more augmentation phases can be performed. Therefore, the total number of augmentation phases is $O(|E|^{\frac{1}{2}})$.

Suppose we have performed $2 |V|^{\frac{2}{3}}$ augmentation phases. Since at most half of the layers ($|V|^{\frac{2}{3}}$ of them) can contain more than $|V|^{\frac{1}{3}}$ vertices, regardless of how the layer sizes are distributed, there is at least one $k$ such that two adjacent layers each contain at most $|V|^{\frac{1}{3}}$ vertices, namely $|D_k| \leq |V|^{\frac{1}{3}}$ and $|D_{k+1}| \leq |V|^{\frac{1}{3}}$.

To maximize the number of edges between $D_k$ and $D_{k+1}$, assume they form a complete bipartite graph. Then the edge set $\left\{ (u, v) \mid u \in D_k, v \in D_{k+1}, (u, v) \in E_f \right\}$ has size at most $|V|^{\frac{2}{3}}$. Clearly, $\{S_k, V - S_k\}$ is a cut in $G_f$ separating $s$ and $t$, and its cut capacity is at most $|V|^{\frac{2}{3}}$. By the max-flow min-cut theorem, the maximum flow in $G_f$ is at most $|V|^{\frac{2}{3}}$, meaning that in $G_f$ at most $|V|^{\frac{2}{3}}$ more augmentation phases can be performed. Therefore, the total number of augmentation phases is $O(|V|^{\frac{2}{3}})$.

We introduce the following lemma: for a network of this form, any flow can always be decomposed into several unit-flow, vertex-disjoint augmenting paths.

Suppose we have performed $|V|^{\frac{1}{2}}$ augmentation phases. By the definition of the level graph, every new augmenting path now has length at least $|V|^{\frac{1}{2}}$.

Consider a decomposition of the maximum flow into augmenting paths in $G_f$. The number of augmenting paths cannot exceed $\frac {|V|} {|V|^{\frac{1}{2}}} \approx |V|^{\frac{1}{2}}$, meaning that at most $|V|^{\frac{1}{2}}$ more augmentation phases can be performed in $G_f$. Therefore, the total number of augmentation phases is $O(|V|^{\frac{1}{2}})$.

struct MF {
  struct edge {
    int v, nxt, cap, flow;
  } e[N];

  int fir[N], cnt = 0;

  int n, S, T;
  ll maxflow = 0;
  int dep[N], cur[N];

  void init() {
    memset(fir, -1, sizeof fir);
    cnt = 0;
  }

  void addedge(int u, int v, int w) {
    e[cnt] = {v, fir[u], w, 0};
    fir[u] = cnt++;
    e[cnt] = {u, fir[v], 0, 0};
    fir[v] = cnt++;
  }

  bool bfs() {
    queue<int> q;
    memset(dep, 0, sizeof(int) * (n + 1));

    dep[S] = 1;
    q.push(S);
    while (q.size()) {
      int u = q.front();
      q.pop();
      for (int i = fir[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if ((!dep[v]) && (e[i].cap > e[i].flow)) {
          dep[v] = dep[u] + 1;
          q.push(v);
        }
      }
    }
    return dep[T];
  }

  int dfs(int u, int flow) {
    if ((u == T) || (!flow)) return flow;

    int ret = 0;
    for (int& i = cur[u]; ~i; i = e[i].nxt) {
      int v = e[i].v, d;
      if ((dep[v] == dep[u] + 1) &&
          (d = dfs(v, min(flow - ret, e[i].cap - e[i].flow)))) {
        ret += d;
        e[i].flow += d;
        e[i ^ 1].flow -= d;
        if (ret == flow) return ret;
      }
    }
    return ret;
  }

  void dinic() {
    while (bfs()) {
      memcpy(cur, fir, sizeof(int) * (n + 1));
      maxflow += dfs(S, INF);
    }
  }
} mf;

The MPM algorithm ends in fewer than $V$ phases. To prove this, we first need to prove two lemmas.

Lemma 1: after each iteration, the distance from $s$ to every vertex does not decrease, that is, $level_{i+1}[v] \ge level_{i}[v]$.

Proof: Fix a phase $i$ and a vertex $v$. Consider in $G_{i}^R$ any shortest path from $s$ to $v$, denoted $P$. The length of $P$ is $level_{i}[v]$. Note that $G_{i}^R$ can contain only backward and forward edges of $G_{i}^R$. If $P$ has no backward edge of $G_{i}^R$, then $level_{i+1}[v] \ge level_{i}[v]$, because $P$ is also a path in $G_{i}^R$. Now suppose that $P$ has at least one backward edge and its first such edge is $(u,w)$. Then $level_{i+1}[u] \ge level_{i}[u]$ (by the first case). The edge $(u,w)$ does not belong to $G_{i}^R$, so $(u,w)$ was affected by the augmenting path of the previous iteration. This means $level_{i}[u] = level_{i}[w]+1$. In addition, $level_{i+1}[w] = level_{i+1}[u]+1$. From these two equations and $level_{i+1}[u] \ge level_{i}[u]$, we get $level_{i+1}[w] \ge level_{i}[w]+2$. The remaining part of the path can be handled in the same way.

Lemma 2: $level_{i+1}[t] > level_{i}[t]$.

Proof: Lemma 1 gives $level_{i+1}[t] \ge level_{i}[t]$. Suppose $level_{i+1}[t] = level_{i}[t]$. Note that $G_{i}^R$ can contain only backward and forward edges of $G_{i}^R$. This means $G_{i}^R$ contains a shortest path that was not blocked by the augmenting path, which is a contradiction.

struct MPM {
  struct FlowEdge {
    int v, u;
    long long cap, flow;

    FlowEdge() {}

    FlowEdge(int _v, int _u, long long _cap, long long _flow)
        : v(_v), u(_u), cap(_cap), flow(_flow) {}

    FlowEdge(int _v, int _u, long long _cap)
        : v(_v), u(_u), cap(_cap), flow(0ll) {}
  };

  constexpr static long long flow_inf = 1e18;
  vector<FlowEdge> edges;
  vector<char> alive;
  vector<long long> pin, pout;
  vector<list<int>> in, out;
  vector<vector<int>> adj;
  vector<long long> ex;
  int n, m = 0;
  int s, t;
  vector<int> level;
  vector<int> q;
  int qh, qt;

  void resize(int _n) {
    n = _n;
    ex.resize(n);
    q.resize(n);
    pin.resize(n);
    pout.resize(n);
    adj.resize(n);
    level.resize(n);
    in.resize(n);
    out.resize(n);
  }

  MPM() {}

  MPM(int _n, int _s, int _t) {
    resize(_n);
    s = _s;
    t = _t;
  }

  void add_edge(int v, int u, long long cap) {
    edges.push_back(FlowEdge(v, u, cap));
    edges.push_back(FlowEdge(u, v, 0));
    adj[v].push_back(m);
    adj[u].push_back(m + 1);
    m += 2;
  }

  bool bfs() {
    while (qh < qt) {
      int v = q[qh++];
      for (int id : adj[v]) {
        if (edges[id].cap - edges[id].flow < 1) continue;
        if (level[edges[id].u] != -1) continue;
        level[edges[id].u] = level[v] + 1;
        q[qt++] = edges[id].u;
      }
    }
    return level[t] != -1;
  }

  long long pot(int v) { return min(pin[v], pout[v]); }

  void remove_node(int v) {
    for (int i : in[v]) {
      int u = edges[i].v;
      auto it = find(out[u].begin(), out[u].end(), i);
      out[u].erase(it);
      pout[u] -= edges[i].cap - edges[i].flow;
    }
    for (int i : out[v]) {
      int u = edges[i].u;
      auto it = find(in[u].begin(), in[u].end(), i);
      in[u].erase(it);
      pin[u] -= edges[i].cap - edges[i].flow;
    }
  }

  void push(int from, int to, long long f, bool forw) {
    qh = qt = 0;
    ex.assign(n, 0);
    ex[from] = f;
    q[qt++] = from;
    while (qh < qt) {
      int v = q[qh++];
      if (v == to) break;
      long long must = ex[v];
      auto it = forw ? out[v].begin() : in[v].begin();
      while (true) {
        int u = forw ? edges[*it].u : edges[*it].v;
        long long pushed = min(must, edges[*it].cap - edges[*it].flow);
        if (pushed == 0) break;
        if (forw) {
          pout[v] -= pushed;
          pin[u] -= pushed;
        } else {
          pin[v] -= pushed;
          pout[u] -= pushed;
        }
        if (ex[u] == 0) q[qt++] = u;
        ex[u] += pushed;
        edges[*it].flow += pushed;
        edges[(*it) ^ 1].flow -= pushed;
        must -= pushed;
        if (edges[*it].cap - edges[*it].flow == 0) {
          auto jt = it;
          ++jt;
          if (forw) {
            in[u].erase(find(in[u].begin(), in[u].end(), *it));
            out[v].erase(it);
          } else {
            out[u].erase(find(out[u].begin(), out[u].end(), *it));
            in[v].erase(it);
          }
          it = jt;
        } else
          break;
        if (!must) break;
      }
    }
  }

  long long flow() {
    long long ans = 0;
    while (true) {
      pin.assign(n, 0);
      pout.assign(n, 0);
      level.assign(n, -1);
      alive.assign(n, true);
      level[s] = 0;
      qh = 0;
      qt = 1;
      q[0] = s;
      if (!bfs()) break;
      for (int i = 0; i < n; i++) {
        out[i].clear();
        in[i].clear();
      }
      for (int i = 0; i < m; i++) {
        if (edges[i].cap - edges[i].flow == 0) continue;
        int v = edges[i].v, u = edges[i].u;
        if (level[v] + 1 == level[u] && (level[u] < level[t] || u == t)) {
          in[u].push_back(i);
          out[v].push_back(i);
          pin[u] += edges[i].cap - edges[i].flow;
          pout[v] += edges[i].cap - edges[i].flow;
        }
      }
      pin[s] = pout[t] = flow_inf;
      while (true) {
        int v = -1;
        for (int i = 0; i < n; i++) {
          if (!alive[i]) continue;
          if (v == -1 || pot(i) < pot(v)) v = i;
        }
        if (v == -1) break;
        if (pot(v) == 0) {
          alive[v] = false;
          remove_node(v);
          continue;
        }
        long long f = pot(v);
        ans += f;
        push(v, s, f, false);
        push(v, t, f, true);
        alive[v] = false;
        remove_node(v);
      }
    }
    return ans;
  }
};

struct Edge {
  int from, to, cap, flow;

  Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

bool operator<(const Edge& a, const Edge& b) {
  return a.from < b.from || (a.from == b.from && a.to < b.to);
}

struct ISAP {
  int n, m, s, t;
  vector<Edge> edges;
  vector<int> G[MAXN];
  bool vis[MAXN];
  int d[MAXN];
  int cur[MAXN];
  int p[MAXN];
  int num[MAXN];

  void AddEdge(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }

  bool BFS() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(t);
    vis[t] = true;
    d[t] = 0;
    while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      for (int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i] ^ 1];
        if (!vis[e.from] && e.cap > e.flow) {
          vis[e.from] = true;
          d[e.from] = d[x] + 1;
          Q.push(e.from);
        }
      }
    }
    return vis[s];
  }

  void init(int n) {
    this->n = n;
    for (int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }

  int Augment() {
    int x = t, a = INF;
    while (x != s) {
      Edge& e = edges[p[x]];
      a = min(a, e.cap - e.flow);
      x = edges[p[x]].from;
    }
    x = t;
    while (x != s) {
      edges[p[x]].flow += a;
      edges[p[x] ^ 1].flow -= a;
      x = edges[p[x]].from;
    }
    return a;
  }

  int Maxflow(int s, int t) {
    this->s = s;
    this->t = t;
    int flow = 0;
    BFS();
    memset(num, 0, sizeof(num));
    for (int i = 0; i < n; i++) num[d[i]]++;
    int x = s;
    memset(cur, 0, sizeof(cur));
    while (d[s] < n) {
      if (x == t) {
        flow += Augment();
        x = s;
      }
      int ok = 0;
      for (int i = cur[x]; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if (e.cap > e.flow && d[x] == d[e.to] + 1) {
          ok = 1;
          p[e.to] = G[x][i];
          cur[x] = i;
          x = e.to;
          break;
        }
      }
      if (!ok) {
        int m = n - 1;
        for (int i = 0; i < G[x].size(); i++) {
          Edge& e = edges[G[x][i]];
          if (e.cap > e.flow) m = min(m, d[e.to]);
        }
        if (--num[d[x]] == 0) break;
        num[d[x] = m + 1]++;
        cur[x] = 0;
        if (x != s) x = edges[p[x]].from;
      }
    }
    return flow;
  }
};

constexpr int N = 1e4 + 4, M = 1e5 + 5, INF = 0x3f3f3f3f;
int n, m, s, t, maxflow, tot;
int ht[N], ex[N];

void init() {  // Initialization
  for (int i = h[s]; i; i = e[i].nex) {
    const int &v = e[i].t;
    ex[v] = e[i].v, ex[s] -= ex[v], e[i ^ 1].v = e[i].v, e[i].v = 0;
  }
  ht[s] = n;
}

bool push(int ed) {
  const int &u = e[ed ^ 1].t, &v = e[ed].t;
  int flow = min(ex[u], e[ed].v);
  ex[u] -= flow, ex[v] += flow, e[ed].v -= flow, e[ed ^ 1].v += flow;
  return ex[u];  // Return 1 if u is still overflowing
}

void relabel(int u) {
  ht[u] = INF;
  for (int i = h[u]; i; i = e[i].nex)
    if (e[i].v) ht[u] = min(ht[u], ht[e[i].t]);
  ++ht[u];
}