graph/GlobalMinCut.h

• View this file on GitHub
• Last update: 2025-11-14 00:13:37+07:00

Code

pair<int, vi> globalMinCut(vector<vi> mat) {
  pair<int, vi> best = {INT_MAX, {}};
  int n = sz(mat);
  vector<vi> co(n);
  for (int i = 0; i < n; ++i) co[i] = {i};
  for (int ph = 1; ph < n; ++ph) {
    vi w = mat[0];
    size_t s = 0, t = 0;
    for (int it = 0; it < n - ph; ++it) {  // O(V^2) -> O(E log V) with prio. queue
      w[t] = INT_MIN;
      s = t, t = max_element(all(w)) - w.begin();
      for (int i = 0; i < n; ++i) w[i] += mat[t][i];
    }
    best = min(best, {w[t] - mat[t][t], co[t]});
    co[s].insert(co[s].end(), all(co[t]));
    for (int i = 0; i < n; ++i) mat[s][i] += mat[t][i];
    for (int i = 0; i < n; ++i) mat[i][s] = mat[s][i];
    mat[0][t] = INT_MIN;
  }
  return best;
}

#line 1 "graph/GlobalMinCut.h"
pair<int, vi> globalMinCut(vector<vi> mat) {
  pair<int, vi> best = {INT_MAX, {}};
  int n = sz(mat);
  vector<vi> co(n);
  for (int i = 0; i < n; ++i) co[i] = {i};
  for (int ph = 1; ph < n; ++ph) {
    vi w = mat[0];
    size_t s = 0, t = 0;
    for (int it = 0; it < n - ph; ++it) {  // O(V^2) -> O(E log V) with prio. queue
      w[t] = INT_MIN;
      s = t, t = max_element(all(w)) - w.begin();
      for (int i = 0; i < n; ++i) w[i] += mat[t][i];
    }
    best = min(best, {w[t] - mat[t][t], co[t]});
    co[s].insert(co[s].end(), all(co[t]));
    for (int i = 0; i < n; ++i) mat[s][i] += mat[t][i];
    for (int i = 0; i < n; ++i) mat[i][s] = mat[s][i];
    mat[0][t] = INT_MIN;
  }
  return best;
}

Back to top page