global_min_cut.hpp¶
Stoer–Wagner 全局最小割，返回割权和确定的割侧；融合候选扫描，避免顶点组复制，遇到零割提前结束。
Complexity: Time: \(O(V^{3})\). Space: \(O(V^{2})\), including the matrix copy. Other workspace is \(O(V)\). A zero phase cut terminates the search early.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V^3). Space: O(V^2), including the matrix copy.
/// Other workspace is O(V). A zero phase cut terminates the search early.
#include <algorithm>
#include <cassert>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Stoer-Wagner global minimum cut, returning its weight and a sorted
/// side. Require a square symmetric nonnegative matrix with zero diagonal;
/// all weights and intermediate sums must be finite and representable in T.
/// The matrix is passed by value; an lvalue input is unchanged. Preserve the
/// original smallest-vertex phase ties and first strictly best cut. For n=0
/// return {0,{}}; for n=1 return {0,{0}}. No recursion or numeric sentinels.
template <class T>
std::pair<T, std::vector<int>> global_min_cut(std::vector<std::vector<T>> w) {
int n = int(w.size());
for (const auto &row : w) {
assert(int(row.size()) == n);
}
for (int i = 0; i < n; ++i) {
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<int> active(n), tail(n), next(n, -1), todo;
std::iota(active.begin(), active.end(), 0);
tail = active;
std::vector<T> con;
T best{};
int begin = -1, end = -1;
while (active.size() > 1) {
int pre = active.front();
todo.assign(active.begin() + 1, active.end());
con.assign(todo.size(), T{});
for (int count = int(todo.size()); count > 0; --count) {
const auto &row = w[pre];
con[0] += row[todo[0]];
T maximum = con[0];
int at = 0;
// Fuse connection-weight updates and selection. Keeping todo sorted
// preserves the smallest original vertex on ties without another test.
for (int i = 1; i < count; ++i) {
con[i] += row[todo[i]];
if (maximum < con[i]) {
maximum = con[i];
at = i;
}
}
int sel = todo[at];
if (count == 1) {
// The first cut is valid even when its weight equals T's maximum.
if (begin == -1 || maximum < best) {
best = maximum;
begin = sel;
end = tail[sel];
}
if (!(T{} < best)) break;
for (int u : active) {
if (u != pre && u != sel) {
w[pre][u] += w[sel][u];
w[u][pre] = w[pre][u];
}
}
// Each merge fills one tail's null link. Saving both endpoints keeps
// a previous best group intact even when its old tail is extended.
next[tail[pre]] = sel;
tail[pre] = tail[sel];
active.erase(std::find(active.begin(), active.end(), sel));
break;
}
todo.erase(todo.begin() + at);
con.erase(con.begin() + at);
pre = sel;
}
if (!(T{} < best)) break;
}
std::vector<int> side;
for (int u = begin;; u = next[u]) {
side.push_back(u);
if (u == end) break;
}
std::sort(side.begin(), side.end());
return {best, std::move(side)};
}
} // namespace noya
// NOYA_GLOBAL_MIN_CUT_HPP
#ifndef NOYA_GLOBAL_MIN_CUT_HPP
#define NOYA_GLOBAL_MIN_CUT_HPP 1
/// @complexity Time: O(V^3). Space: O(V^2), including the matrix copy.
/// Other workspace is O(V). A zero phase cut terminates the search early.
#include <algorithm>
#include <cassert>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Stoer-Wagner global minimum cut, returning its weight and a sorted
/// side. Require a square symmetric nonnegative matrix with zero diagonal;
/// all weights and intermediate sums must be finite and representable in T.
/// The matrix is passed by value; an lvalue input is unchanged. Preserve the
/// original smallest-vertex phase ties and first strictly best cut. For n=0
/// return {0,{}}; for n=1 return {0,{0}}. No recursion or numeric sentinels.
template <class T>
std::pair<T, std::vector<int>> global_min_cut(std::vector<std::vector<T>> w) {
int n = int(w.size());
for (const auto &row : w) {
assert(int(row.size()) == n);
}
for (int i = 0; i < n; ++i) {
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<int> active(n), tail(n), next(n, -1), todo;
std::iota(active.begin(), active.end(), 0);
tail = active;
std::vector<T> con;
T best{};
int begin = -1, end = -1;
while (active.size() > 1) {
int pre = active.front();
todo.assign(active.begin() + 1, active.end());
con.assign(todo.size(), T{});
for (int count = int(todo.size()); count > 0; --count) {
const auto &row = w[pre];
con[0] += row[todo[0]];
T maximum = con[0];
int at = 0;
// Fuse connection-weight updates and selection. Keeping todo sorted
// preserves the smallest original vertex on ties without another test.
for (int i = 1; i < count; ++i) {
con[i] += row[todo[i]];
if (maximum < con[i]) {
maximum = con[i];
at = i;
}
}
int sel = todo[at];
if (count == 1) {
// The first cut is valid even when its weight equals T's maximum.
if (begin == -1 || maximum < best) {
best = maximum;
begin = sel;
end = tail[sel];
}
if (!(T{} < best)) break;
for (int u : active) {
if (u != pre && u != sel) {
w[pre][u] += w[sel][u];
w[u][pre] = w[pre][u];
}
}
// Each merge fills one tail's null link. Saving both endpoints keeps
// a previous best group intact even when its old tail is extended.
next[tail[pre]] = sel;
tail[pre] = tail[sel];
active.erase(std::find(active.begin(), active.end(), sel));
break;
}
todo.erase(todo.begin() + at);
con.erase(con.begin() + at);
pre = sel;
}
if (!(T{} < best)) break;
}
std::vector<int> side;
for (int u = begin;; u = next[u]) {
side.push_back(u);
if (u == end) break;
}
std::sort(side.begin(), side.end());
return {best, std::move(side)};
}
} // namespace noya
#endif // NOYA_GLOBAL_MIN_CUT_HPP
/// @complexity Time: O(V^3). Space: O(V^2), including the matrix copy.
/// Other workspace is O(V). A zero phase cut terminates the search early.
#include <algorithm>
#include <cassert>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Stoer-Wagner global minimum cut, returning its weight and a sorted
/// side. Require a square symmetric nonnegative matrix with zero diagonal;
/// all weights and intermediate sums must be finite and representable in T.
/// The matrix is passed by value; an lvalue input is unchanged. Preserve the
/// original smallest-vertex phase ties and first strictly best cut. For n=0
/// return {0,{}}; for n=1 return {0,{0}}. No recursion or numeric sentinels.
template <class T>
std::pair<T, std::vector<int>> global_min_cut(std::vector<std::vector<T>> w) {
int n = int(w.size());
for (const auto &row : w) {
assert(int(row.size()) == n);
}
for (int i = 0; i < n; ++i) {
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<int> active(n), tail(n), next(n, -1), todo;
std::iota(active.begin(), active.end(), 0);
tail = active;
std::vector<T> con;
T best{};
int begin = -1, end = -1;
while (active.size() > 1) {
int pre = active.front();
todo.assign(active.begin() + 1, active.end());
con.assign(todo.size(), T{});
for (int count = int(todo.size()); count > 0; --count) {
const auto &row = w[pre];
con[0] += row[todo[0]];
T maximum = con[0];
int at = 0;
// Fuse connection-weight updates and selection. Keeping todo sorted
// preserves the smallest original vertex on ties without another test.
for (int i = 1; i < count; ++i) {
con[i] += row[todo[i]];
if (maximum < con[i]) {
maximum = con[i];
at = i;
}
}
int sel = todo[at];
if (count == 1) {
// The first cut is valid even when its weight equals T's maximum.
if (begin == -1 || maximum < best) {
best = maximum;
begin = sel;
end = tail[sel];
}
if (!(T{} < best)) break;
for (int u : active) {
if (u != pre && u != sel) {
w[pre][u] += w[sel][u];
w[u][pre] = w[pre][u];
}
}
// Each merge fills one tail's null link. Saving both endpoints keeps
// a previous best group intact even when its old tail is extended.
next[tail[pre]] = sel;
tail[pre] = tail[sel];
active.erase(std::find(active.begin(), active.end(), sel));
break;
}
todo.erase(todo.begin() + at);
con.erase(con.begin() + at);
pre = sel;
}
if (!(T{} < best)) break;
}
std::vector<int> side;
for (int u = begin;; u = next[u]) {
side.push_back(u);
if (u == end) break;
}
std::sort(side.begin(), side.end());
return {best, std::move(side)};
}
} // namespace noya
// NOYA_GLOBAL_MIN_CUT_HPP