bipartite_matching.hpp¶
求二分图最大匹配，并可据此恢复最小点覆盖等结构；适合左右两类对象的一对一配对。
Complexity: Time: O(E sqrt(V)) sparse; dense variant scans bitsets per augmenting search. Space: O(V + E), or O(V^2 / word_size) for dense adjacency.
AC 记录：bipartitematching。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(E sqrt(V)) sparse; dense variant scans bitsets per augmenting search.
/// Space: O(V + E), or O(V^2 / word_size) for dense adjacency.
#include <algorithm>
#include <bitset>
#include <cassert>
#include <random>
#include <utility>
#include <vector>
namespace noya {
/// @brief Dense bipartite matching using bitset-accelerated augmenting paths.
template <typename BS> struct BipartiteMatching_Dense {
int N1, N2;
std::vector<BS> &adj;
std::vector<int> m1, m2;
std::vector<int> que;
std::vector<int> pre;
BS vis;
BipartiteMatching_Dense(std::vector<BS> &adj, int N1, int N2)
: N1(N1), N2(N2), adj(adj), m1(N1, -1), m2(N2, -1) {
for (int s = 0; s < N1; s++)
bfs(s);
}
void bfs(int s) {
if (m1[s] != -1)
return;
que.resize(N1), pre.resize(N1);
int l = 0, r = 0;
vis.set(), pre[s] = -1;
que[r++] = s;
while (l < r) {
int u = que[l++];
BS can = vis & adj[u];
for (int v = can._Find_first(); v < N2; v = can._Find_next(v)) {
vis[v] = 0;
if (m2[v] != -1) {
que[r++] = m2[v];
pre[m2[v]] = u;
continue;
}
int a = u, b = v;
while (a != -1) {
int t = m1[a];
m1[a] = b, m2[b] = a, a = pre[a], b = t;
}
return;
}
}
return;
}
/// @brief Return all matched pairs (left_vertex, right_vertex).
std::vector<std::pair<int, int>> matching() {
std::vector<std::pair<int, int>> res;
for (int v = 0; v < N1; v++)
if (m1[v] != -1)
res.emplace_back(v, m1[v]);
return res;
}
/// @brief Compute minimum vertex cover as (left_vertices, right_vertices).
std::pair<std::vector<int>, std::vector<int>> vertex_cover() {
std::vector<int> que(N1);
int l = 0, r = 0;
vis.set();
std::vector<bool> ok(N1);
for (int i = 0; i < N1; i++) {
if (m1[i] == -1)
ok[i] = 1, que[r++] = i;
}
while (l < r) {
int a = que[l++];
BS can = adj[a] & vis;
for (int b = can._Find_first(); b < N2; b = can._Find_next(b)) {
vis[b] = 0;
int to = m2[b];
assert(to != -1);
if (!ok[to])
ok[to] = 1, que[r++] = to;
}
}
std::vector<int> l1, r1;
for (int i = 0; i < N1; i++)
if (!ok[i])
l1.emplace_back(i);
for (int i = 0; i < N2; i++)
if (!vis[i])
r1.emplace_back(i);
return {l1, r1};
}
};
/// @brief Hopcroft-Karp maximum bipartite matching in O(E sqrt(V)).
struct HopcroftKarp {
std::vector<int> g, l, r;
int ans;
HopcroftKarp(int n, int m, std::vector<std::pair<int, int>> &e)
: g(e.size()), l(n, -1), r(m, -1), ans(0) {
std::mt19937 rng(0);
std::shuffle(e.begin(), e.end(), rng);
std::vector<int> deg(n + 1), a, p, q(n);
for (auto &[x, y] : e)
deg[x]++;
for (int i = 1; i <= n; i++)
deg[i] += deg[i - 1];
for (auto &[x, y] : e)
g[--deg[x]] = y;
for (bool mat = true; mat;) {
a.assign(n, -1);
p.assign(n, -1);
int t = 0;
mat = false;
for (int i = 0; i < n; i++)
if (l[i] == -1)
q[t++] = a[i] = p[i] = i;
for (int i = 0; i < t; i++) {
int x = q[i];
if (~l[a[x]])
continue;
for (int j = deg[x]; j < deg[x + 1]; j++) {
int y = g[j];
if (r[y] == -1) {
while (~y) {
r[y] = x;
std::swap(l[x], y);
x = p[x];
}
mat = true;
ans++;
break;
}
if (p[r[y]] == -1) {
q[t++] = y = r[y];
p[y] = x;
a[y] = a[x];
}
}
}
}
}
};
} // namespace noya
#ifndef NOYA_BIPARTITE_MATCHING_HPP
#define NOYA_BIPARTITE_MATCHING_HPP 1
/// @complexity Time: O(E sqrt(V)) sparse; dense variant scans bitsets per augmenting search.
/// Space: O(V + E), or O(V^2 / word_size) for dense adjacency.
#include <algorithm>
#include <bitset>
#include <cassert>
#include <random>
#include <utility>
#include <vector>
namespace noya {
/// @brief Dense bipartite matching using bitset-accelerated augmenting paths.
template <typename BS> struct BipartiteMatching_Dense {
int N1, N2;
std::vector<BS> &adj;
std::vector<int> m1, m2;
std::vector<int> que;
std::vector<int> pre;
BS vis;
BipartiteMatching_Dense(std::vector<BS> &adj, int N1, int N2)
: N1(N1), N2(N2), adj(adj), m1(N1, -1), m2(N2, -1) {
for (int s = 0; s < N1; s++)
bfs(s);
}
void bfs(int s) {
if (m1[s] != -1)
return;
que.resize(N1), pre.resize(N1);
int l = 0, r = 0;
vis.set(), pre[s] = -1;
que[r++] = s;
while (l < r) {
int u = que[l++];
BS can = vis & adj[u];
for (int v = can._Find_first(); v < N2; v = can._Find_next(v)) {
vis[v] = 0;
if (m2[v] != -1) {
que[r++] = m2[v];
pre[m2[v]] = u;
continue;
}
int a = u, b = v;
while (a != -1) {
int t = m1[a];
m1[a] = b, m2[b] = a, a = pre[a], b = t;
}
return;
}
}
return;
}
/// @brief Return all matched pairs (left_vertex, right_vertex).
std::vector<std::pair<int, int>> matching() {
std::vector<std::pair<int, int>> res;
for (int v = 0; v < N1; v++)
if (m1[v] != -1)
res.emplace_back(v, m1[v]);
return res;
}
/// @brief Compute minimum vertex cover as (left_vertices, right_vertices).
std::pair<std::vector<int>, std::vector<int>> vertex_cover() {
std::vector<int> que(N1);
int l = 0, r = 0;
vis.set();
std::vector<bool> ok(N1);
for (int i = 0; i < N1; i++) {
if (m1[i] == -1)
ok[i] = 1, que[r++] = i;
}
while (l < r) {
int a = que[l++];
BS can = adj[a] & vis;
for (int b = can._Find_first(); b < N2; b = can._Find_next(b)) {
vis[b] = 0;
int to = m2[b];
assert(to != -1);
if (!ok[to])
ok[to] = 1, que[r++] = to;
}
}
std::vector<int> l1, r1;
for (int i = 0; i < N1; i++)
if (!ok[i])
l1.emplace_back(i);
for (int i = 0; i < N2; i++)
if (!vis[i])
r1.emplace_back(i);
return {l1, r1};
}
};
/// @brief Hopcroft-Karp maximum bipartite matching in O(E sqrt(V)).
struct HopcroftKarp {
std::vector<int> g, l, r;
int ans;
HopcroftKarp(int n, int m, std::vector<std::pair<int, int>> &e)
: g(e.size()), l(n, -1), r(m, -1), ans(0) {
std::mt19937 rng(0);
std::shuffle(e.begin(), e.end(), rng);
std::vector<int> deg(n + 1), a, p, q(n);
for (auto &[x, y] : e)
deg[x]++;
for (int i = 1; i <= n; i++)
deg[i] += deg[i - 1];
for (auto &[x, y] : e)
g[--deg[x]] = y;
for (bool mat = true; mat;) {
a.assign(n, -1);
p.assign(n, -1);
int t = 0;
mat = false;
for (int i = 0; i < n; i++)
if (l[i] == -1)
q[t++] = a[i] = p[i] = i;
for (int i = 0; i < t; i++) {
int x = q[i];
if (~l[a[x]])
continue;
for (int j = deg[x]; j < deg[x + 1]; j++) {
int y = g[j];
if (r[y] == -1) {
while (~y) {
r[y] = x;
std::swap(l[x], y);
x = p[x];
}
mat = true;
ans++;
break;
}
if (p[r[y]] == -1) {
q[t++] = y = r[y];
p[y] = x;
a[y] = a[x];
}
}
}
}
}
};
} // namespace noya
#endif // NOYA_BIPARTITE_MATCHING_HPP
#include <algorithm>
#include <bitset>
#include <cassert>
#include <random>
#include <utility>
#include <vector>
/// @complexity Time: O(E sqrt(V)) sparse; dense variant scans bitsets per augmenting search.
/// Space: O(V + E), or O(V^2 / word_size) for dense adjacency.
namespace noya {
/// @brief Dense bipartite matching using bitset-accelerated augmenting paths.
template <typename BS> struct BipartiteMatching_Dense {
int N1, N2;
std::vector<BS> &adj;
std::vector<int> m1, m2;
std::vector<int> que;
std::vector<int> pre;
BS vis;
BipartiteMatching_Dense(std::vector<BS> &adj, int N1, int N2)
: N1(N1), N2(N2), adj(adj), m1(N1, -1), m2(N2, -1) {
for (int s = 0; s < N1; s++)
bfs(s);
}
void bfs(int s) {
if (m1[s] != -1)
return;
que.resize(N1), pre.resize(N1);
int l = 0, r = 0;
vis.set(), pre[s] = -1;
que[r++] = s;
while (l < r) {
int u = que[l++];
BS can = vis & adj[u];
for (int v = can._Find_first(); v < N2; v = can._Find_next(v)) {
vis[v] = 0;
if (m2[v] != -1) {
que[r++] = m2[v];
pre[m2[v]] = u;
continue;
}
int a = u, b = v;
while (a != -1) {
int t = m1[a];
m1[a] = b, m2[b] = a, a = pre[a], b = t;
}
return;
}
}
return;
}
/// @brief Return all matched pairs (left_vertex, right_vertex).
std::vector<std::pair<int, int>> matching() {
std::vector<std::pair<int, int>> res;
for (int v = 0; v < N1; v++)
if (m1[v] != -1)
res.emplace_back(v, m1[v]);
return res;
}
/// @brief Compute minimum vertex cover as (left_vertices, right_vertices).
std::pair<std::vector<int>, std::vector<int>> vertex_cover() {
std::vector<int> que(N1);
int l = 0, r = 0;
vis.set();
std::vector<bool> ok(N1);
for (int i = 0; i < N1; i++) {
if (m1[i] == -1)
ok[i] = 1, que[r++] = i;
}
while (l < r) {
int a = que[l++];
BS can = adj[a] & vis;
for (int b = can._Find_first(); b < N2; b = can._Find_next(b)) {
vis[b] = 0;
int to = m2[b];
assert(to != -1);
if (!ok[to])
ok[to] = 1, que[r++] = to;
}
}
std::vector<int> l1, r1;
for (int i = 0; i < N1; i++)
if (!ok[i])
l1.emplace_back(i);
for (int i = 0; i < N2; i++)
if (!vis[i])
r1.emplace_back(i);
return {l1, r1};
}
};
/// @brief Hopcroft-Karp maximum bipartite matching in O(E sqrt(V)).
struct HopcroftKarp {
std::vector<int> g, l, r;
int ans;
HopcroftKarp(int n, int m, std::vector<std::pair<int, int>> &e)
: g(e.size()), l(n, -1), r(m, -1), ans(0) {
std::mt19937 rng(0);
std::shuffle(e.begin(), e.end(), rng);
std::vector<int> deg(n + 1), a, p, q(n);
for (auto &[x, y] : e)
deg[x]++;
for (int i = 1; i <= n; i++)
deg[i] += deg[i - 1];
for (auto &[x, y] : e)
g[--deg[x]] = y;
for (bool mat = true; mat;) {
a.assign(n, -1);
p.assign(n, -1);
int t = 0;
mat = false;
for (int i = 0; i < n; i++)
if (l[i] == -1)
q[t++] = a[i] = p[i] = i;
for (int i = 0; i < t; i++) {
int x = q[i];
if (~l[a[x]])
continue;
for (int j = deg[x]; j < deg[x + 1]; j++) {
int y = g[j];
if (r[y] == -1) {
while (~y) {
r[y] = x;
std::swap(l[x], y);
x = p[x];
}
mat = true;
ans++;
break;
}
if (p[r[y]] == -1) {
q[t++] = y = r[y];
p[y] = x;
a[y] = a[x];
}
}
}
}
}
};
} // namespace noya