Dinic

Code

#include <vector>
#include <queue>

struct dinic {
  using cap_type = int;
  const cap_type INF = 1e9;
  struct edge {
    int to;
    cap_type cap;
    int rev;
  };
  int n;
  std::vector<std::vector<edge>> g;

  dinic(int n): n(n), g(n) {}

  void add_edge(int from, int to, cap_type cap, cap_type rev_cap = 0) {
    g[from].push_back({ to, cap, (int)(g[to].size()) });
    g[to].push_back({ from, rev_cap, (int)(g[from].size() - 1) });
  }
  
  std::vector<int> level;
  std::vector<int> iter;
  cap_type dfs(const int s, const int v, cap_type mf) {
    if(s == v || mf == 0) return mf;
    for(int& i = iter[v]; i < g[v].size(); i++) {
      int t = g[v][i].to;
      edge& re = g[v][i];
      edge& e = g[t][re.rev];
      if(level[t] >= level[v] || e.cap == 0) continue;
      cap_type f = dfs(s, t, std::min(mf, e.cap));
      if(f == 0) continue;
      e.cap -= f;
      re.cap += f;
      return f;
    }
    return 0;
  }

  cap_type max_flow(int s, int t) {
    std::vector<int> que(n);
    cap_type flow = 0;
    while(true) {
      level.assign(n, -1);
      int qi = 0;
      int qr = 0;
      level[s] = 0;
      que[qr++] = s;
      while(qi < qr && level[t]) {
        int v = que[qi++];
        for(const auto& e: g[v]) {
          if(e.cap > 0 && level[e.to] == -1) {
            level[e.to] = level[v] + 1;
            que[qr++] = e.to;
          }
        }
      }
      if(level[t] == -1) break;
      iter.assign(n, 0);
      cap_type tmp;
      while((tmp = dfs(s, t, INF)) > 0) {
        flow += tmp;
      }
    }
    return flow;
  }
};