(useless) MaximumFlow (Edmond Karp)

use Dinic instead.

template <typename T>
struct MaximumFlow {
  struct Edge {
    int to;
    T cap;
  };

  int n;
  std::vector<Edge> edges;
  std::vector<std::vector<int>> g;

  MaximumFlow(int _n) : n(_n) {
    g.resize(n);
  }

  void addEdge(int u, int v, T cap) {
    assert(0 <= u && u < n && 0 <= v && v < n);
    assert(cap >= 0);
    g[u].push_back(int(edges.size()));
    edges.push_back({v, cap});
    g[v].push_back(int(edges.size()));
    edges.push_back({u, 0});
  }

  T augment(int s, int t) {
    std::vector<int> from(n, -1);
    from[s] = -2;
    std::vector<int> que(1, s);
    for (int b = 0; b < int(que.size()); ++b) {
      int x = que[b];
      for (const auto& eid : g[x]) {
        const auto& e = edges[eid];
        if (e.cap != 0 && from[e.to] == -1) {
          from[e.to] = eid;
          que.push_back(e.to);
        }
      }
    }
    if (from[t] == -1) {
      return 0;
    }
    T inc = std::numeric_limits<T>::max();
    {
      int cur = t;
      while (cur != s) {
        inc = std::min(inc, edges[from[cur]].cap);
        cur = edges[from[cur] ^ 1].to;
      }
    }
    {
      int cur = t;
      while (cur != s) {
        edges[from[cur]].cap -= inc;
        edges[from[cur] ^ 1].cap += inc;
        cur = edges[from[cur] ^ 1].to;
      }
    }
    return inc;
  }

  T solve(int s, int t) {
    assert(0 <= s && s < n && 0 <= t && t < n && s != t);
    T flow = 0;
    while (true) {
      T inc = augment(s, t);
      if (inc == 0) {
        break;
      }
      flow += inc;
    }
    return flow;
  }

  std::vector<bool> minCut(int s, int t) {
    std::vector<bool> res(n);
    std::vector<int> que(1, s);
    res[s] = true;
    for (int b = 0; b < int(que.size()); ++b) {
      int x = que[b];
      for (const auto& eid : g[x]) {
        const auto& e = edges[eid];
        if (e.cap != 0 && !res[e.to]) {
          que.push_back(e.to);
          res[e.to] = true;
        }
      }
    }
    return res;
  }
};