graph/Dinic.h

• View this file on GitHub
• Last update: 2025-11-28 10:18:48+07:00

Required by

• graph/GomoryHu.h

Verified with

• tests/Bipartite_Matching_Dinic.test.cpp

Code

struct Dinic {
  struct Edge {
    int to, rev;
    i64 c, oc;
    i64 flow() { return max(oc - c, i64(0)); }  // if you need flows
  };
  vi lvl, ptr, q;
  vector<vector<Edge>> adj;
  Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
  void addEdge(int a, int b, i64 c, i64 rcap = 0) {
    adj[a].pb({b, sz(adj[b]), c, c});
    adj[b].pb({a, sz(adj[a]) - 1, rcap, rcap});
  }
  i64 dfs(int v, int t, i64 f) {
    if (v == t || !f) return f;
    for (int& i = ptr[v]; i < sz(adj[v]); i++) {
      Edge& e = adj[v][i];
      if (lvl[e.to] == lvl[v] + 1)
        if (i64 p = dfs(e.to, t, min(f, e.c))) {
          e.c -= p, adj[e.to][e.rev].c += p;
          return p;
        }
    }
    return 0;
  }
  i64 calc(int s, int t) {
    i64 flow = 0;
    q[0] = s;
    // 'int L=30' maybe faster for random data
    for (int L = 0; L < 31; ++L) {
      do {
        lvl = ptr = vi(sz(q));
        int qi = 0, qe = lvl[s] = 1;
        while (qi < qe && !lvl[t]) {
          int v = q[qi++];
          for (Edge e : adj[v])
            if (!lvl[e.to] && e.c >> (30 - L))
              q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
        }
        while (i64 p = dfs(s, t, LLONG_MAX)) flow += p;
      } while (lvl[t]);
    }
    return flow;
  }
  bool leftOfMinCut(int a) { return lvl[a] != 0; }
};

#line 1 "graph/Dinic.h"
struct Dinic {
  struct Edge {
    int to, rev;
    i64 c, oc;
    i64 flow() { return max(oc - c, i64(0)); }  // if you need flows
  };
  vi lvl, ptr, q;
  vector<vector<Edge>> adj;
  Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
  void addEdge(int a, int b, i64 c, i64 rcap = 0) {
    adj[a].pb({b, sz(adj[b]), c, c});
    adj[b].pb({a, sz(adj[a]) - 1, rcap, rcap});
  }
  i64 dfs(int v, int t, i64 f) {
    if (v == t || !f) return f;
    for (int& i = ptr[v]; i < sz(adj[v]); i++) {
      Edge& e = adj[v][i];
      if (lvl[e.to] == lvl[v] + 1)
        if (i64 p = dfs(e.to, t, min(f, e.c))) {
          e.c -= p, adj[e.to][e.rev].c += p;
          return p;
        }
    }
    return 0;
  }
  i64 calc(int s, int t) {
    i64 flow = 0;
    q[0] = s;
    // 'int L=30' maybe faster for random data
    for (int L = 0; L < 31; ++L) {
      do {
        lvl = ptr = vi(sz(q));
        int qi = 0, qe = lvl[s] = 1;
        while (qi < qe && !lvl[t]) {
          int v = q[qi++];
          for (Edge e : adj[v])
            if (!lvl[e.to] && e.c >> (30 - L))
              q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
        }
        while (i64 p = dfs(s, t, LLONG_MAX)) flow += p;
      } while (lvl[t]);
    }
    return flow;
  }
  bool leftOfMinCut(int a) { return lvl[a] != 0; }
};

Back to top page