general_matching.hpp¶
用带花树求一般无向图最大基数匹配；适合图不保证二分的配对问题。
Complexity: Time: O(V^3). Space: O(V^2).
AC 记录：general_matching。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V^3).
/// Space: O(V^2).
#include <algorithm>
#include <cassert>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
namespace general_matching_internal {
struct solver {
int n;
std::vector<std::vector<int>> g;
std::vector<int> mat, fa, bas;
std::vector<bool> vis, bl;
solver(int n_, const std::vector<std::pair<int, int>> &es)
: n(n_), g(n), mat(n, -1), fa(n), bas(n), vis(n), bl(n) {
assert(n >= 0);
for (auto [u, v] : es) {
assert(0 <= u && u < n);
assert(0 <= v && v < n);
if (u != v) {
g[u].push_back(v);
g[v].push_back(u);
}
}
}
int least_common_ancestor(int a, int b) {
std::vector<bool> on(n);
while (true) {
a = bas[a];
on[a] = true;
if (mat[a] == -1) {
break;
}
a = fa[mat[a]];
}
while (true) {
b = bas[b];
if (on[b]) {
return b;
}
b = fa[mat[b]];
}
}
void mark_path(int x, int cb, int v1) {
while (bas[x] != cb) {
bl[bas[x]] = true;
bl[bas[mat[x]]] = true;
fa[x] = v1;
v1 = mat[x];
x = fa[mat[x]];
}
}
bool augment_from(int rt) {
std::fill(vis.begin(), vis.end(), false);
std::fill(fa.begin(), fa.end(), -1);
std::iota(bas.begin(), bas.end(), 0);
std::queue<int> q;
q.push(rt);
vis[rt] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int to : g[x]) {
if (bas[x] == bas[to] || mat[x] == to) {
continue;
}
if (to == rt || (mat[to] != -1 && fa[mat[to]] != -1)) {
int cb = least_common_ancestor(x, to);
std::fill(bl.begin(), bl.end(), false);
mark_path(x, cb, to);
mark_path(to, cb, x);
for (int i = 0; i < n; i++) {
if (!bl[bas[i]]) {
continue;
}
bas[i] = cb;
if (!vis[i]) {
vis[i] = true;
q.push(i);
}
}
} else if (fa[to] == -1) {
fa[to] = x;
if (mat[to] == -1) {
for (int cur = to; cur != -1;) {
int pre = fa[cur];
int nxt = pre == -1 ? -1 : mat[pre];
mat[cur] = pre;
if (pre != -1) {
mat[pre] = cur;
}
cur = nxt;
}
return true;
}
to = mat[to];
vis[to] = true;
q.push(to);
}
}
}
return false;
}
std::pair<int, std::vector<int>> run() {
int siz = 0;
for (int x = 0; x < n; x++) {
if (mat[x] == -1 && augment_from(x)) {
siz++;
}
}
return {siz, mat};
}
};
} // namespace general_matching_internal
/// @brief Maximum matching in a general undirected graph in O(n^3).
/// @return (matching size, mate of every vertex), with -1 for unmatched
/// vertices.
inline std::pair<int, std::vector<int>>
maximum_matching(int n, const std::vector<std::pair<int, int>> &es) {
return general_matching_internal::solver(n, es).run();
}
} // namespace noya
#ifndef NOYA_GENERAL_MATCHING_HPP
#define NOYA_GENERAL_MATCHING_HPP 1
/// @complexity Time: O(V^3).
/// Space: O(V^2).
#include <algorithm>
#include <cassert>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
namespace general_matching_internal {
struct solver {
int n;
std::vector<std::vector<int>> g;
std::vector<int> mat, fa, bas;
std::vector<bool> vis, bl;
solver(int n_, const std::vector<std::pair<int, int>> &es)
: n(n_), g(n), mat(n, -1), fa(n), bas(n), vis(n), bl(n) {
assert(n >= 0);
for (auto [u, v] : es) {
assert(0 <= u && u < n);
assert(0 <= v && v < n);
if (u != v) {
g[u].push_back(v);
g[v].push_back(u);
}
}
}
int least_common_ancestor(int a, int b) {
std::vector<bool> on(n);
while (true) {
a = bas[a];
on[a] = true;
if (mat[a] == -1) {
break;
}
a = fa[mat[a]];
}
while (true) {
b = bas[b];
if (on[b]) {
return b;
}
b = fa[mat[b]];
}
}
void mark_path(int x, int cb, int v1) {
while (bas[x] != cb) {
bl[bas[x]] = true;
bl[bas[mat[x]]] = true;
fa[x] = v1;
v1 = mat[x];
x = fa[mat[x]];
}
}
bool augment_from(int rt) {
std::fill(vis.begin(), vis.end(), false);
std::fill(fa.begin(), fa.end(), -1);
std::iota(bas.begin(), bas.end(), 0);
std::queue<int> q;
q.push(rt);
vis[rt] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int to : g[x]) {
if (bas[x] == bas[to] || mat[x] == to) {
continue;
}
if (to == rt || (mat[to] != -1 && fa[mat[to]] != -1)) {
int cb = least_common_ancestor(x, to);
std::fill(bl.begin(), bl.end(), false);
mark_path(x, cb, to);
mark_path(to, cb, x);
for (int i = 0; i < n; i++) {
if (!bl[bas[i]]) {
continue;
}
bas[i] = cb;
if (!vis[i]) {
vis[i] = true;
q.push(i);
}
}
} else if (fa[to] == -1) {
fa[to] = x;
if (mat[to] == -1) {
for (int cur = to; cur != -1;) {
int pre = fa[cur];
int nxt = pre == -1 ? -1 : mat[pre];
mat[cur] = pre;
if (pre != -1) {
mat[pre] = cur;
}
cur = nxt;
}
return true;
}
to = mat[to];
vis[to] = true;
q.push(to);
}
}
}
return false;
}
std::pair<int, std::vector<int>> run() {
int siz = 0;
for (int x = 0; x < n; x++) {
if (mat[x] == -1 && augment_from(x)) {
siz++;
}
}
return {siz, mat};
}
};
} // namespace general_matching_internal
/// @brief Maximum matching in a general undirected graph in O(n^3).
/// @return (matching size, mate of every vertex), with -1 for unmatched
/// vertices.
inline std::pair<int, std::vector<int>>
maximum_matching(int n, const std::vector<std::pair<int, int>> &es) {
return general_matching_internal::solver(n, es).run();
}
} // namespace noya
#endif // NOYA_GENERAL_MATCHING_HPP
#include <algorithm>
#include <cassert>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
/// @complexity Time: O(V^3).
/// Space: O(V^2).
namespace noya {
namespace general_matching_internal {
struct solver {
int n;
std::vector<std::vector<int>> g;
std::vector<int> mat, fa, bas;
std::vector<bool> vis, bl;
solver(int n_, const std::vector<std::pair<int, int>> &es)
: n(n_), g(n), mat(n, -1), fa(n), bas(n), vis(n), bl(n) {
assert(n >= 0);
for (auto [u, v] : es) {
assert(0 <= u && u < n);
assert(0 <= v && v < n);
if (u != v) {
g[u].push_back(v);
g[v].push_back(u);
}
}
}
int least_common_ancestor(int a, int b) {
std::vector<bool> on(n);
while (true) {
a = bas[a];
on[a] = true;
if (mat[a] == -1) {
break;
}
a = fa[mat[a]];
}
while (true) {
b = bas[b];
if (on[b]) {
return b;
}
b = fa[mat[b]];
}
}
void mark_path(int x, int cb, int v1) {
while (bas[x] != cb) {
bl[bas[x]] = true;
bl[bas[mat[x]]] = true;
fa[x] = v1;
v1 = mat[x];
x = fa[mat[x]];
}
}
bool augment_from(int rt) {
std::fill(vis.begin(), vis.end(), false);
std::fill(fa.begin(), fa.end(), -1);
std::iota(bas.begin(), bas.end(), 0);
std::queue<int> q;
q.push(rt);
vis[rt] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int to : g[x]) {
if (bas[x] == bas[to] || mat[x] == to) {
continue;
}
if (to == rt || (mat[to] != -1 && fa[mat[to]] != -1)) {
int cb = least_common_ancestor(x, to);
std::fill(bl.begin(), bl.end(), false);
mark_path(x, cb, to);
mark_path(to, cb, x);
for (int i = 0; i < n; i++) {
if (!bl[bas[i]]) {
continue;
}
bas[i] = cb;
if (!vis[i]) {
vis[i] = true;
q.push(i);
}
}
} else if (fa[to] == -1) {
fa[to] = x;
if (mat[to] == -1) {
for (int cur = to; cur != -1;) {
int pre = fa[cur];
int nxt = pre == -1 ? -1 : mat[pre];
mat[cur] = pre;
if (pre != -1) {
mat[pre] = cur;
}
cur = nxt;
}
return true;
}
to = mat[to];
vis[to] = true;
q.push(to);
}
}
}
return false;
}
std::pair<int, std::vector<int>> run() {
int siz = 0;
for (int x = 0; x < n; x++) {
if (mat[x] == -1 && augment_from(x)) {
siz++;
}
}
return {siz, mat};
}
};
} // namespace general_matching_internal
/// @brief Maximum matching in a general undirected graph in O(n^3).
/// @return (matching size, mate of every vertex), with -1 for unmatched
/// vertices.
inline std::pair<int, std::vector<int>>
maximum_matching(int n, const std::vector<std::pair<int, int>> &es) {
return general_matching_internal::solver(n, es).run();
}
} // namespace noya