global_min_cut.hpp¶

SECTIONGraph INCLUDEnoya/global_min_cut.hpp

求无向带权图不指定端点的全局最小割，并恢复割的一个侧集。

Complexity: Time: O(V^3). Space: O(V^2).

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(V^3).
/// Space: O(V^2).

#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>

namespace noya {

/// @brief Stoer-Wagner global minimum cut of an undirected weighted graph in
/// O(n^3), returning (cut weight, one side of the cut).
template <class T>
std::pair<T, std::vector<int>> global_min_cut(std::vector<std::vector<T>> w) {
  int n = int(w.size());
  for (int i = 0; i < n; i++) {
    assert(int(w[i].size()) == n);
    assert(w[i][i] == T{});
    for (int j = 0; j < n; j++) {
      assert(w[i][j] == w[j][i] && !(w[i][j] < T{}));
    }
  }
  if (n <= 1) {
    return {T{}, n == 0 ? std::vector<int>{} : std::vector<int>{0}};
  }

  std::vector<bool> act(n, true);
  std::vector<std::vector<int>> grp(n);
  for (int i = 0; i < n; i++) {
    grp[i] = {i};
  }
  T bst = std::numeric_limits<T>::max();
  std::vector<int> bs;
  for (int sz = n; sz > 1; sz--) {
    std::vector<T> con(n);
    std::vector<bool> add(n);
    int pre = -1;
    for (int stp = 0; stp < sz; stp++) {
      int sel = -1;
      for (int u = 0; u < n; u++) {
        if (act[u] && !add[u] && (sel == -1 || con[sel] < con[u])) {
          sel = u;
        }
      }
      assert(sel != -1);
      if (stp + 1 == sz) {
        if (con[sel] < bst) {
          bst = con[sel];
          bs = grp[sel];
        }
        for (int u = 0; u < n; u++) {
          if (act[u] && u != pre) {
            w[pre][u] += w[sel][u];
            w[u][pre] = w[pre][u];
          }
        }
        grp[pre].insert(grp[pre].end(), grp[sel].begin(), grp[sel].end());
        act[sel] = false;
        break;
      }
      add[sel] = true;
      pre = sel;
      for (int u = 0; u < n; u++) {
        if (act[u] && !add[u]) {
          con[u] += w[sel][u];
        }
      }
    }
  }
  std::sort(bs.begin(), bs.end());
  return {bst, bs};
}

} // namespace noya

#ifndef NOYA_GLOBAL_MIN_CUT_HPP
#define NOYA_GLOBAL_MIN_CUT_HPP 1

/// @complexity Time: O(V^3).
/// Space: O(V^2).

#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>

namespace noya {

/// @brief Stoer-Wagner global minimum cut of an undirected weighted graph in
/// O(n^3), returning (cut weight, one side of the cut).
template <class T>
std::pair<T, std::vector<int>> global_min_cut(std::vector<std::vector<T>> w) {
  int n = int(w.size());
  for (int i = 0; i < n; i++) {
    assert(int(w[i].size()) == n);
    assert(w[i][i] == T{});
    for (int j = 0; j < n; j++) {
      assert(w[i][j] == w[j][i] && !(w[i][j] < T{}));
    }
  }
  if (n <= 1) {
    return {T{}, n == 0 ? std::vector<int>{} : std::vector<int>{0}};
  }

  std::vector<bool> act(n, true);
  std::vector<std::vector<int>> grp(n);
  for (int i = 0; i < n; i++) {
    grp[i] = {i};
  }
  T bst = std::numeric_limits<T>::max();
  std::vector<int> bs;
  for (int sz = n; sz > 1; sz--) {
    std::vector<T> con(n);
    std::vector<bool> add(n);
    int pre = -1;
    for (int stp = 0; stp < sz; stp++) {
      int sel = -1;
      for (int u = 0; u < n; u++) {
        if (act[u] && !add[u] && (sel == -1 || con[sel] < con[u])) {
          sel = u;
        }
      }
      assert(sel != -1);
      if (stp + 1 == sz) {
        if (con[sel] < bst) {
          bst = con[sel];
          bs = grp[sel];
        }
        for (int u = 0; u < n; u++) {
          if (act[u] && u != pre) {
            w[pre][u] += w[sel][u];
            w[u][pre] = w[pre][u];
          }
        }
        grp[pre].insert(grp[pre].end(), grp[sel].begin(), grp[sel].end());
        act[sel] = false;
        break;
      }
      add[sel] = true;
      pre = sel;
      for (int u = 0; u < n; u++) {
        if (act[u] && !add[u]) {
          con[u] += w[sel][u];
        }
      }
    }
  }
  std::sort(bs.begin(), bs.end());
  return {bst, bs};
}

} // namespace noya

#endif // NOYA_GLOBAL_MIN_CUT_HPP

#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>

/// @complexity Time: O(V^3).
/// Space: O(V^2).

namespace noya {

/// @brief Stoer-Wagner global minimum cut of an undirected weighted graph in
/// O(n^3), returning (cut weight, one side of the cut).
template <class T>
std::pair<T, std::vector<int>> global_min_cut(std::vector<std::vector<T>> w) {
  int n = int(w.size());
  for (int i = 0; i < n; i++) {
    assert(int(w[i].size()) == n);
    assert(w[i][i] == T{});
    for (int j = 0; j < n; j++) {
      assert(w[i][j] == w[j][i] && !(w[i][j] < T{}));
    }
  }
  if (n <= 1) {
    return {T{}, n == 0 ? std::vector<int>{} : std::vector<int>{0}};
  }

  std::vector<bool> act(n, true);
  std::vector<std::vector<int>> grp(n);
  for (int i = 0; i < n; i++) {
    grp[i] = {i};
  }
  T bst = std::numeric_limits<T>::max();
  std::vector<int> bs;
  for (int sz = n; sz > 1; sz--) {
    std::vector<T> con(n);
    std::vector<bool> add(n);
    int pre = -1;
    for (int stp = 0; stp < sz; stp++) {
      int sel = -1;
      for (int u = 0; u < n; u++) {
        if (act[u] && !add[u] && (sel == -1 || con[sel] < con[u])) {
          sel = u;
        }
      }
      assert(sel != -1);
      if (stp + 1 == sz) {
        if (con[sel] < bst) {
          bst = con[sel];
          bs = grp[sel];
        }
        for (int u = 0; u < n; u++) {
          if (act[u] && u != pre) {
            w[pre][u] += w[sel][u];
            w[u][pre] = w[pre][u];
          }
        }
        grp[pre].insert(grp[pre].end(), grp[sel].begin(), grp[sel].end());
        act[sel] = false;
        break;
      }
      add[sel] = true;
      pre = sel;
      for (int u = 0; u < n; u++) {
        if (act[u] && !add[u]) {
          con[u] += w[sel][u];
        }
      }
    }
  }
  std::sort(bs.begin(), bs.end());
  return {bst, bs};
}

} // namespace noya