graph/GomoryHu.h

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

Depends on

• graph/Dinic.h

Code

#include "Dinic.h"

typedef array<i64, 3> Edge;
vector<Edge> gomoryHu(int N, vector<Edge> ed) {
  vector<Edge> tree;
  vi par(N);
  for (int i = 1; i < N; ++i) {
    Dinic D(N);
    for (Edge t : ed) D.addEdge(t[0], t[1], t[2], t[2]);
    tree.push_back({i, par[i], D.calc(i, par[i])});
    for (int j = i + 1; j < N; ++j)
      if (par[j] == par[i] && D.leftOfMinCut(j)) par[j] = i;
  }
  return tree;
}

#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; }
};
#line 2 "graph/GomoryHu.h"

typedef array<i64, 3> Edge;
vector<Edge> gomoryHu(int N, vector<Edge> ed) {
  vector<Edge> tree;
  vi par(N);
  for (int i = 1; i < N; ++i) {
    Dinic D(N);
    for (Edge t : ed) D.addEdge(t[0], t[1], t[2], t[2]);
    tree.push_back({i, par[i], D.calc(i, par[i])});
    for (int j = i + 1; j < N; ++j)
      if (par[j] == par[i] && D.leftOfMinCut(j)) par[j] = i;
  }
  return tree;
}

Back to top page