Some Templates

Maximum Flow (Minimum Cut)

template < class T, int N, int M >
struct MaxFlow {
  int cnt = 1, head[N], nxt[M << 1], node[M << 1], dep[N], cur[N], n, flow_sink;
  T flows[M << 1];
  void add_edge (int u, int v, T w) {
    cnt ++, nxt[cnt] = head[u], head[u] = cnt, node[cnt] = v, flows[cnt] = w;
    cnt ++, nxt[cnt] = head[v], head[v] = cnt, node[cnt] = u, flows[cnt] = 0;
    return ;
  }
  T dfs (int u, T remain) {
    if (u == flow_sink) return remain;
    T res = 0;
    for (int i = cur[u]; i && remain; i = nxt[i]) {
      cur[u] = i;
      T f = std :: min (remain, flows[i]);
      int v = node[i];
      if (dep[u] + 1 == dep[v] && f) {
        T f_ = dfs (v, f);
        res += f_, remain -= f_;
        flows[i] -= f_, flows[i ^ 1] += f_;
      }
    }
    if (!res) dep[u] = -1;
    return res;
  }
  T Flow (int source, int sink) {
    flow_sink = sink;
    T res = 0;
    while (true) {
      std :: queue < int > q;
      while (!q.empty ()) q.pop ();
      for (int i = 0;i <= n; ++ i) cur[i] = head[i], dep[i] = -1;
      q.push (source), dep[source] = 0;
      while (!q.empty ()) {
        int u = q.front ();
        q.pop ();
        for (int i = head[u]; i ; i = nxt[i]) {
          if (dep[node[i]] == -1 && flows[i]) {
            dep[node[i]] = dep[u] + 1;
            q.push (node[i]);
          }
        }
      }
      if (dep[sink] == -1) return res;
      res += dfs (source, 1e18);
    }
    return 0;
  }
  void init (int n_) {
    n = n_;
    cnt = 1;
    for (int i = 1;i <= n; ++ i) head[i] = 0;
    return ;
  }
};