global_min_cut.hpp¶
Stoer-Wagner global minimum cut of an undirected weighted graph in O(n^3), returning (cut weight, one side of the cut).
求无向带权图不指定端点的全局最小割，并恢复割的一个侧集。
Implementation¶
#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>> weight) {
int n = int(weight.size());
for (int i = 0; i < n; i++) {
assert(int(weight[i].size()) == n);
assert(weight[i][i] == T{});
for (int j = 0; j < n; j++) {
assert(weight[i][j] == weight[j][i] && !(weight[i][j] < T{}));
}
}
if (n <= 1) {
return {T{}, n == 0 ? std::vector<int>{} : std::vector<int>{0}};
}
std::vector<bool> active(n, true);
std::vector<std::vector<int>> group(n);
for (int i = 0; i < n; i++) {
group[i] = {i};
}
T best = std::numeric_limits<T>::max();
std::vector<int> best_side;
for (int phase_size = n; phase_size > 1; phase_size--) {
std::vector<T> connection(n);
std::vector<bool> added(n);
int previous = -1;
for (int step = 0; step < phase_size; step++) {
int selected = -1;
for (int vertex = 0; vertex < n; vertex++) {
if (active[vertex] && !added[vertex] &&
(selected == -1 || connection[selected] < connection[vertex])) {
selected = vertex;
}
}
assert(selected != -1);
if (step + 1 == phase_size) {
if (connection[selected] < best) {
best = connection[selected];
best_side = group[selected];
}
for (int vertex = 0; vertex < n; vertex++) {
if (active[vertex] && vertex != previous) {
weight[previous][vertex] += weight[selected][vertex];
weight[vertex][previous] = weight[previous][vertex];
}
}
group[previous].insert(group[previous].end(), group[selected].begin(),
group[selected].end());
active[selected] = false;
break;
}
added[selected] = true;
previous = selected;
for (int vertex = 0; vertex < n; vertex++) {
if (active[vertex] && !added[vertex]) {
connection[vertex] += weight[selected][vertex];
}
}
}
}
std::sort(best_side.begin(), best_side.end());
return {best, best_side};
}
} // 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>> weight) {
int n = int(weight.size());
for (int i = 0; i < n; i++) {
assert(int(weight[i].size()) == n);
assert(weight[i][i] == T{});
for (int j = 0; j < n; j++) {
assert(weight[i][j] == weight[j][i] && !(weight[i][j] < T{}));
}
}
if (n <= 1) {
return {T{}, n == 0 ? std::vector<int>{} : std::vector<int>{0}};
}
std::vector<bool> active(n, true);
std::vector<std::vector<int>> group(n);
for (int i = 0; i < n; i++) {
group[i] = {i};
}
T best = std::numeric_limits<T>::max();
std::vector<int> best_side;
for (int phase_size = n; phase_size > 1; phase_size--) {
std::vector<T> connection(n);
std::vector<bool> added(n);
int previous = -1;
for (int step = 0; step < phase_size; step++) {
int selected = -1;
for (int vertex = 0; vertex < n; vertex++) {
if (active[vertex] && !added[vertex] &&
(selected == -1 || connection[selected] < connection[vertex])) {
selected = vertex;
}
}
assert(selected != -1);
if (step + 1 == phase_size) {
if (connection[selected] < best) {
best = connection[selected];
best_side = group[selected];
}
for (int vertex = 0; vertex < n; vertex++) {
if (active[vertex] && vertex != previous) {
weight[previous][vertex] += weight[selected][vertex];
weight[vertex][previous] = weight[previous][vertex];
}
}
group[previous].insert(group[previous].end(), group[selected].begin(),
group[selected].end());
active[selected] = false;
break;
}
added[selected] = true;
previous = selected;
for (int vertex = 0; vertex < n; vertex++) {
if (active[vertex] && !added[vertex]) {
connection[vertex] += weight[selected][vertex];
}
}
}
}
std::sort(best_side.begin(), best_side.end());
return {best, best_side};
}
} // namespace noya