Dinitz reference implementation

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

typedef long long ll;

const ll INF = 1e18 + 1000;

// A reference implementation of Dinitz's algorithm
// Note: this implementation has been created with educational
// value in mind, not efficiency. Other implementations with
// better constant factors exist; if you're looking for a black
// box to use in a contest, you're better off looking elsewhere.
// See more: https://codeforces.com/blog/entry/104960

// This struct represents the state of an edge, together with its
// reverse edge that may appear in some G_f, during the execution
// of the algorithm.
struct Edge {
  int from, to; // The edge is from->to in the original graph.
  ll capac, flow;

  // Gets the endpoint other than u of the edge.
  int oth (int u) {
    return u ^ from ^ to; // xor trick
  }

  // Gets the capacity of the edge u->oth(u) in G_f.
  ll capacity (int u) {
    if (u == from) {
      return capac - flow;
    } else {
      return flow;
    }
  }

  // Returns whether the edge u->oth(u) exists in u.
  bool exists (int u) {
    return capacity(u) != 0;
  }

  // Adds df flow to the edge in G if u == from,
  // subtracts it otherwise.
  void add_flow (int u, ll df) {
    if (u == from) {
      flow += df;
    } else {
      flow -= df;
    }
  }
};

// At any given time, represents one particular G_f. We modify this class on the
// fly when adding a flow.
class MaxFlow {
  // number of vertices
  int n;
  int source, sink;

  // adj[u] is the set of edges incident to u
  vector<vector<Edge*>> adj;

  // we also keep a list of all edges, for easy retrieval of flow on edge
  vector<Edge*> edges;

  // lvl[u] is the layer (or distance from s) at the current DAG.
  // updated via dinitz_bfs
  vector<int> lvl;

  void dinitz_bfs () {
    // we use a value greater than n to denote "unexplored"
    // or what is called "undefined" in the blog. no vertex actually
    // has a distance greater than n.
    lvl = vector<int> (n, n + 10);

    queue<int> Q;
    Q.push(source);
    lvl[source] = 0;

    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();

      for (auto e : adj[u]) {
        if (!e->exists(u)) {
          continue;
        }

        int v = e->oth(u);
        if (lvl[v] > n) {
          lvl[v] = lvl[u] + 1;
          Q.push(v);
        }

        // in the actual implementation, we don't explicitly add edges to the
        // DAG. we simply say that an edge u->v is in the DAG if lvl[v] = lvl[u] + 1
      }
    }
  }

  bool in_current_dag (int u, int v) {
    return lvl[v] == lvl[u] + 1;
  }

  // as in the blog, tries to push F flow from u
  // returns how much flow could actually be pushed
  // the third parameter is used to maintain what is
  // called v.blocked in the blog; note that it is a
  // reference.
  ll dinitz_dfs (int u, ll F, vector<int> &blocked) {
    if (u == sink) {
      return F;
    }

    ll flow_pushed = 0;
    bool all_blocked = true;
    for (auto e : adj[u]) {
      int v = e->oth(u);
      if (!in_current_dag(u, v)) {
        continue;
      }

      if (e->exists(u) && !blocked[v]) {
        // note that here we use e->capacity(u) instead of
        // the e.capacity - e.flow in the blog, as the Edge
        // struct automatically modifies the capacities when
        // we add flow.
        ll dF = dinitz_dfs(v, min(F, e->capacity(u)), blocked);

        flow_pushed += dF;
        F -= dF;
        e->add_flow(u, dF);
      }

      if (e->exists(u) && !blocked[v]) {
        all_blocked = false;
      }
    }

    if (all_blocked) {
      blocked[u] = true;
    }

    return flow_pushed;
  }

  void dinitz_dfs () {
    vector<int> blocked (n, false);
    dinitz_dfs(source, INF, blocked);
  }

public:
  MaxFlow (int _source, int _sink, const vector<tuple<int, int, ll>> &_edges)
    : source(_source), sink(_sink) {
    n = max(1 + source, 1 + sink);
    for (auto e : _edges) {
      n = max(n, max(1 + get<0>(e), 1 + get<1>(e)));
    }

    adj = vector<vector<Edge*>> (n, vector<Edge*> (0));
    for (auto e : _edges) {
      auto ee = new Edge();
      ee->from = get<0>(e);
      ee->to = get<1>(e);
      ee->flow = 0;
      ee->capac = get<2>(e);

      edges.push_back(ee);
      if (ee->from != ee->to) {
        // don't add self-loops to the adjacency list; they don't do anything
        // useful to the graph and may mess up the algorithm.
        adj[ee->from].push_back(ee);
        adj[ee->to].push_back(ee);
      }
    }
  }

  ll calc_max_flow () {
    while (true) {
      dinitz_bfs();
      if (lvl[sink] > n) {
        // t is not reachable from s anymore.
        break;
      }
      dinitz_dfs();
    }

    ll ans = 0;
    for (auto e : adj[source]) {
      if (e->from == source) {
        ans += e->flow;
      } else {
        ans -= e->flow;
      }
    }

    return ans;
  }

  ll flow_on_edge (int idx) {
    return edges[idx]->flow;
  }
};

// convenience class for building the graph without awkward make_tuples
class GraphBuilder {
  int source, sink;
  vector<tuple<int, int, ll>> edges;

public:
  GraphBuilder (int _source, int _sink) : source(_source), sink(_sink), edges(0) {}

  void add_edge (int u, int v, ll capacity) {
    edges.push_back(make_tuple(u, v, capacity));
  }

  MaxFlow build () {
    return MaxFlow(source, sink, edges);
  }
};

int main () {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, m;
  cin >> n >> m;

  GraphBuilder gb (1, n);
  for (int i = 0; i < m; i++) {
    int u, v;
    ll capac;
    cin >> u >> v >> capac;

    gb.add_edge(u, v, capac);
    // in case of undirected edges:
    // gb.add_edge(v, u, capac);
  }

  auto mf = gb.build();
  ll ans = mf.calc_max_flow();
  cout << ans << '\n';
}