Find Max flow of a network using Dinic's algorithm.

Dinic.cpp

#include <climits>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

constexpr int MAXN{100 * 1000};

struct Edge {
  // beg --edge--> dest
  // dest, current flow(residual), capacity, index of beg in alist[dest]
  int v, flow, cap, idx_u;
  Edge(int V, int Flow, int Cap, int Idx_u)
      : v(V), flow(Flow), cap(Cap), idx_u(Idx_u) {}
};

int n, m, src, trgt;
int depth[MAXN], nxt[MAXN];
vector<Edge> alist[MAXN];

bool BFS(int s) {
  memset(depth, -1, n * sizeof(depth[0]));
  depth[s] = 0;
  queue<int> q;

  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (size_t i = 0; i < alist[u].size(); i++) {
      Edge &e = alist[u][i];
      // not seen? && is it completely flooded?
      if (depth[e.v] == -1 && e.flow < e.cap) {
        depth[e.v] = depth[u] + 1;
        q.push(e.v);
      }
    }
  }
  return depth[trgt] > -1; // did we reach the sink?
}

int DFS(int s, int flow) // dfs
{
  if (s == trgt)
    return flow;

  for (int &i = nxt[s]; i < static_cast<int>(alist[s].size()); i++) {
    Edge &e = alist[s][i];
    if (depth[e.v] == depth[s] + 1 && e.flow < e.cap) {
      int new_flow = DFS(e.v, min(e.cap - e.flow, flow));
      if (new_flow > 0) {
        e.flow += new_flow;
        alist[e.v][e.idx_u].flow -= new_flow; // residual
        return new_flow;
      }
    }
  }
  return 0; // couldn't reach sink node
}

int dinic() {
  if (src == trgt)
    return -1;

  int total_flow = 0;
  while (BFS(src)) {
    memset(nxt, 0, n * sizeof(nxt[0])); // I spent 3 hrs on this line: sizeof
    while (int flow_augpth = DFS(src, INT_MAX))
      total_flow += flow_augpth;
  }
  return total_flow;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  cin >> n >> m >> src >> trgt;

  for (int i = 0; i < m; ++i) {
    int u, v, c;
    cin >> u >> v >> c;
    Edge fwd{v, 0, c, static_cast<int>(alist[v].size())},
        backwd{u, 0, 0, static_cast<int>(alist[u].size())};
    alist[u].push_back(fwd);
    alist[v].push_back(backwd);
  }

  cout << dinic() << endl;
  return 0;
}