bipartite_matching.hpp¶
稀疏二分图最大匹配与稠密位集匹配；稠密版还可恢复最小点覆盖。支持重边、空图和长增广路；稀疏版不再打乱输入，稠密版支持动态位集和增边后增广。
Complexity: Time: \(O(V + E \sqrt{V})\) sparse; \(O(V + W + N_{1} \cdot (N_{1} \cdot W + N_{2}))\) dense, with \(W\) words per row. Space: \(O(V + E)\) sparse; \(O(V + W)\) dense auxiliary plus \(O(N_{1} \cdot W)\) adjacency.
Source: maspy (dense matcher)
AC 记录：bipartitematching。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V + E sqrt(V)) sparse;
/// O(V + W + N1 * (N1 * W + N2)) dense, with W words per row.
/// Space: O(V + E) sparse; O(V + W) dense auxiliary plus O(N1 * W) adjacency.
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
namespace noya {
namespace bipartite_matching_internal {
// GNU bitset and noya::dynamic_bitset have different find-next conventions.
// Other bitsets (including libc++ std::bitset) use a portable bitwise scan.
// For that fallback, replace W by the row's bit capacity in the time bound.
// dynamic_bitset is supplied by noya/ds/dynamic_bitset.hpp when needed.
template <class BS> std::size_t first(const BS &bits) {
if constexpr (requires { bits._Find_first(); }) return bits._Find_first();
else if constexpr (requires { bits.find_first(); }) return bits.find_first();
else {
for (std::size_t i = 0; i < bits.size(); ++i) if (bits[i]) return i;
return bits.size();
}
}
template <class BS> std::size_t next(const BS &bits, std::size_t pos) {
if constexpr (requires { bits._Find_next(pos); }) return bits._Find_next(pos);
else if constexpr (requires { bits.find_next(pos); }) return bits.find_next(pos + 1);
else {
for (++pos; pos < bits.size(); ++pos) if (bits[pos]) return pos;
return bits.size();
}
}
} // namespace bipartite_matching_internal
/// @brief Dense bipartite matching with bitset augmenting paths. Adjacency is
/// borrowed and unchanged; it must outlive this object. The first N1 rows have
/// equal capacities >= N2. Bits at positions >= N2 are ignored.
/// Supports GNU/libc++ std::bitset and noya::dynamic_bitset; only GNU and the
/// dynamic bitset provide word-efficient set-bit search.
template <typename BS> struct BipartiteMatching_Dense {
int N1, N2;
std::vector<BS> &adj;
std::vector<int> m1, m2, que, pre;
BS vis;
BipartiteMatching_Dense(std::vector<BS> &adj_, int n, int m)
: N1(n), N2(m), adj(adj_), m1(n, -1), m2(m, -1),
vis(adj_.empty() ? BS{} : adj_.front()) {
assert(n >= 0 && m >= 0 && adj.size() >= std::size_t(n));
for (int u = 0; u < n; ++u)
assert(adj[u].size() == vis.size() && adj[u].size() >= std::size_t(m));
using bipartite_matching_internal::first;
BS free = vis;
free.set();
std::vector<int> pending;
int count = 0, target = std::min(n, m);
for (int u = 0; u < n && count < target; ++u) {
if (first(adj[u]) >= std::size_t(m)) continue;
BS can = adj[u] & free;
std::size_t v = first(can);
if (v < std::size_t(m)) {
m1[u] = int(v);
m2[v] = u;
free.reset(v);
++count;
} else {
pending.push_back(u);
}
}
BS available = vis;
available.set();
for (int s : pending) {
if (count == target) break;
count += augment(s, available);
}
}
/// @brief Try one augmentation from an unmatched left vertex. After adding
/// edges, call this for every unmatched left vertex to restore maximal size.
/// The current matching must remain valid; graph dimensions cannot change.
void bfs(int s) {
assert(0 <= s && s < N1);
if (m1[s] != -1) return;
BS available = vis;
available.set(); // Do not reuse failed-search pruning after graph edits.
augment(s, available);
}
/// @brief Return matched pairs in increasing left-vertex order.
std::vector<std::pair<int, int>> matching() const {
std::vector<std::pair<int, int>> result;
for (int u = 0; u < N1; ++u)
if (m1[u] != -1) result.emplace_back(u, m1[u]);
return result;
}
/// @brief Minimum vertex cover as two increasing vertex lists. Requires a
/// maximum matching; does not change matching arrays or input adjacency.
std::pair<std::vector<int>, std::vector<int>> vertex_cover() {
using namespace bipartite_matching_internal;
std::vector<int> queue;
std::vector<bool> reached(N1);
for (int u = 0; u < N1; ++u)
if (m1[u] == -1) { reached[u] = true; queue.push_back(u); }
vis.set();
for (std::size_t head = 0; head < queue.size(); ++head) {
BS can = adj[queue[head]] & vis;
for (std::size_t v = first(can); v < std::size_t(N2); v = next(can, v)) {
vis.reset(v);
int u = m2[v];
assert(u != -1);
if (!reached[u]) { reached[u] = true; queue.push_back(u); }
}
}
std::vector<int> left, right;
for (int u = 0; u < N1; ++u) if (!reached[u]) left.push_back(u);
for (int v = 0; v < N2; ++v)
if (m2[v] != -1 && reached[m2[v]]) right.push_back(v);
return {std::move(left), std::move(right)};
}
private:
bool augment(int s, BS &available) {
using namespace bipartite_matching_internal;
que.resize(N1);
pre.resize(N1);
vis = available;
pre[s] = -1;
int head = 0, tail = 0;
que[tail++] = s;
while (head < tail) {
int u = que[head++];
BS can = adj[u] & vis;
for (std::size_t v = first(can); v < std::size_t(N2); v = next(can, v)) {
vis.reset(v);
if (m2[v] != -1) {
int to = m2[v];
que[tail++] = to;
pre[to] = u;
continue;
}
int a = u, b = int(v);
while (a != -1) {
int previous = m1[a];
m1[a] = b;
m2[b] = a;
a = pre[a];
b = previous;
}
return true;
}
}
// The failed reachable region is closed and has no free right vertex.
// Later augmentations cannot enter and leave it, so it stays unusable
// while this constructor's graph is fixed. Keep it excluded across roots.
available = vis;
return false;
}
};
/// @brief Maximum bipartite matching; l/r contain partners or -1, ans is its
/// size. Duplicate edges are allowed. Input order is preserved, unlike the old
/// shuffled implementation; the optimal witness is not canonical.
struct HopcroftKarp {
std::vector<int> g, l, r;
int ans = 0;
HopcroftKarp(int n, int m, const std::vector<std::pair<int, int>> &edges)
: g(edges.size()), l(n, -1), r(m, -1) {
assert(n >= 0 && m >= 0);
std::vector<std::size_t> off(std::size_t(n) + 1);
for (auto [u, v] : edges) {
assert(0 <= u && u < n && 0 <= v && v < m);
++off[u + 1];
}
for (int u = 0; u < n; ++u) off[u + 1] += off[u];
auto cur = off;
for (auto [u, v] : edges) g[cur[u]++] = v;
std::vector<int> active;
for (int u = 0; u < n; ++u) {
if (off[u] == off[u + 1]) continue;
active.push_back(u);
for (std::size_t i = off[u]; i < off[u + 1]; ++i) {
int v = g[i];
if (r[v] == -1) { l[u] = v; r[v] = u; ++ans; break; }
}
}
int target = std::min(int(active.size()), m);
if (ans == target) return;
std::vector<int> dist(n, -1), queue;
queue.reserve(active.size());
while (ans < target) {
for (int u : active) dist[u] = -1;
queue.clear();
for (int u : active)
if (l[u] == -1) { dist[u] = 0; queue.push_back(u); }
bool found = false;
for (std::size_t head = 0; head < queue.size(); ++head) {
int u = queue[head];
for (std::size_t i = off[u]; i < off[u + 1]; ++i) {
int to = r[g[i]];
if (to == -1) found = true;
else if (dist[to] == -1) {
dist[to] = dist[u] + 1;
queue.push_back(to);
}
}
}
if (!found) break;
// Consume each left vertex once per phase, including successful paths.
auto dfs = [&](auto &self, int u) -> bool {
int depth = dist[u];
dist[u] = -1;
for (auto i = off[u]; i < off[u + 1]; ++i) {
int v = g[i], to = r[v];
if (to == -1 || (dist[to] == depth + 1 && self(self, to))) {
l[u] = v;
r[v] = u;
return true;
}
}
return false;
};
for (int u : active)
if (l[u] == -1 && dfs(dfs, u)) ++ans;
}
}
};
} // namespace noya
// NOYA_BIPARTITE_MATCHING_HPP
#ifndef NOYA_BIPARTITE_MATCHING_HPP
#define NOYA_BIPARTITE_MATCHING_HPP 1
/// @complexity Time: O(V + E sqrt(V)) sparse;
/// O(V + W + N1 * (N1 * W + N2)) dense, with W words per row.
/// Space: O(V + E) sparse; O(V + W) dense auxiliary plus O(N1 * W) adjacency.
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
namespace noya {
namespace bipartite_matching_internal {
// GNU bitset and noya::dynamic_bitset have different find-next conventions.
// Other bitsets (including libc++ std::bitset) use a portable bitwise scan.
// For that fallback, replace W by the row's bit capacity in the time bound.
// dynamic_bitset is supplied by noya/ds/dynamic_bitset.hpp when needed.
template <class BS> std::size_t first(const BS &bits) {
if constexpr (requires { bits._Find_first(); }) return bits._Find_first();
else if constexpr (requires { bits.find_first(); }) return bits.find_first();
else {
for (std::size_t i = 0; i < bits.size(); ++i) if (bits[i]) return i;
return bits.size();
}
}
template <class BS> std::size_t next(const BS &bits, std::size_t pos) {
if constexpr (requires { bits._Find_next(pos); }) return bits._Find_next(pos);
else if constexpr (requires { bits.find_next(pos); }) return bits.find_next(pos + 1);
else {
for (++pos; pos < bits.size(); ++pos) if (bits[pos]) return pos;
return bits.size();
}
}
} // namespace bipartite_matching_internal
/// @brief Dense bipartite matching with bitset augmenting paths. Adjacency is
/// borrowed and unchanged; it must outlive this object. The first N1 rows have
/// equal capacities >= N2. Bits at positions >= N2 are ignored.
/// Supports GNU/libc++ std::bitset and noya::dynamic_bitset; only GNU and the
/// dynamic bitset provide word-efficient set-bit search.
template <typename BS> struct BipartiteMatching_Dense {
int N1, N2;
std::vector<BS> &adj;
std::vector<int> m1, m2, que, pre;
BS vis;
BipartiteMatching_Dense(std::vector<BS> &adj_, int n, int m)
: N1(n), N2(m), adj(adj_), m1(n, -1), m2(m, -1),
vis(adj_.empty() ? BS{} : adj_.front()) {
assert(n >= 0 && m >= 0 && adj.size() >= std::size_t(n));
for (int u = 0; u < n; ++u)
assert(adj[u].size() == vis.size() && adj[u].size() >= std::size_t(m));
using bipartite_matching_internal::first;
BS free = vis;
free.set();
std::vector<int> pending;
int count = 0, target = std::min(n, m);
for (int u = 0; u < n && count < target; ++u) {
if (first(adj[u]) >= std::size_t(m)) continue;
BS can = adj[u] & free;
std::size_t v = first(can);
if (v < std::size_t(m)) {
m1[u] = int(v);
m2[v] = u;
free.reset(v);
++count;
} else {
pending.push_back(u);
}
}
BS available = vis;
available.set();
for (int s : pending) {
if (count == target) break;
count += augment(s, available);
}
}
/// @brief Try one augmentation from an unmatched left vertex. After adding
/// edges, call this for every unmatched left vertex to restore maximal size.
/// The current matching must remain valid; graph dimensions cannot change.
void bfs(int s) {
assert(0 <= s && s < N1);
if (m1[s] != -1) return;
BS available = vis;
available.set(); // Do not reuse failed-search pruning after graph edits.
augment(s, available);
}
/// @brief Return matched pairs in increasing left-vertex order.
std::vector<std::pair<int, int>> matching() const {
std::vector<std::pair<int, int>> result;
for (int u = 0; u < N1; ++u)
if (m1[u] != -1) result.emplace_back(u, m1[u]);
return result;
}
/// @brief Minimum vertex cover as two increasing vertex lists. Requires a
/// maximum matching; does not change matching arrays or input adjacency.
std::pair<std::vector<int>, std::vector<int>> vertex_cover() {
using namespace bipartite_matching_internal;
std::vector<int> queue;
std::vector<bool> reached(N1);
for (int u = 0; u < N1; ++u)
if (m1[u] == -1) { reached[u] = true; queue.push_back(u); }
vis.set();
for (std::size_t head = 0; head < queue.size(); ++head) {
BS can = adj[queue[head]] & vis;
for (std::size_t v = first(can); v < std::size_t(N2); v = next(can, v)) {
vis.reset(v);
int u = m2[v];
assert(u != -1);
if (!reached[u]) { reached[u] = true; queue.push_back(u); }
}
}
std::vector<int> left, right;
for (int u = 0; u < N1; ++u) if (!reached[u]) left.push_back(u);
for (int v = 0; v < N2; ++v)
if (m2[v] != -1 && reached[m2[v]]) right.push_back(v);
return {std::move(left), std::move(right)};
}
private:
bool augment(int s, BS &available) {
using namespace bipartite_matching_internal;
que.resize(N1);
pre.resize(N1);
vis = available;
pre[s] = -1;
int head = 0, tail = 0;
que[tail++] = s;
while (head < tail) {
int u = que[head++];
BS can = adj[u] & vis;
for (std::size_t v = first(can); v < std::size_t(N2); v = next(can, v)) {
vis.reset(v);
if (m2[v] != -1) {
int to = m2[v];
que[tail++] = to;
pre[to] = u;
continue;
}
int a = u, b = int(v);
while (a != -1) {
int previous = m1[a];
m1[a] = b;
m2[b] = a;
a = pre[a];
b = previous;
}
return true;
}
}
// The failed reachable region is closed and has no free right vertex.
// Later augmentations cannot enter and leave it, so it stays unusable
// while this constructor's graph is fixed. Keep it excluded across roots.
available = vis;
return false;
}
};
/// @brief Maximum bipartite matching; l/r contain partners or -1, ans is its
/// size. Duplicate edges are allowed. Input order is preserved, unlike the old
/// shuffled implementation; the optimal witness is not canonical.
struct HopcroftKarp {
std::vector<int> g, l, r;
int ans = 0;
HopcroftKarp(int n, int m, const std::vector<std::pair<int, int>> &edges)
: g(edges.size()), l(n, -1), r(m, -1) {
assert(n >= 0 && m >= 0);
std::vector<std::size_t> off(std::size_t(n) + 1);
for (auto [u, v] : edges) {
assert(0 <= u && u < n && 0 <= v && v < m);
++off[u + 1];
}
for (int u = 0; u < n; ++u) off[u + 1] += off[u];
auto cur = off;
for (auto [u, v] : edges) g[cur[u]++] = v;
std::vector<int> active;
for (int u = 0; u < n; ++u) {
if (off[u] == off[u + 1]) continue;
active.push_back(u);
for (std::size_t i = off[u]; i < off[u + 1]; ++i) {
int v = g[i];
if (r[v] == -1) { l[u] = v; r[v] = u; ++ans; break; }
}
}
int target = std::min(int(active.size()), m);
if (ans == target) return;
std::vector<int> dist(n, -1), queue;
queue.reserve(active.size());
while (ans < target) {
for (int u : active) dist[u] = -1;
queue.clear();
for (int u : active)
if (l[u] == -1) { dist[u] = 0; queue.push_back(u); }
bool found = false;
for (std::size_t head = 0; head < queue.size(); ++head) {
int u = queue[head];
for (std::size_t i = off[u]; i < off[u + 1]; ++i) {
int to = r[g[i]];
if (to == -1) found = true;
else if (dist[to] == -1) {
dist[to] = dist[u] + 1;
queue.push_back(to);
}
}
}
if (!found) break;
// Consume each left vertex once per phase, including successful paths.
auto dfs = [&](auto &self, int u) -> bool {
int depth = dist[u];
dist[u] = -1;
for (auto i = off[u]; i < off[u + 1]; ++i) {
int v = g[i], to = r[v];
if (to == -1 || (dist[to] == depth + 1 && self(self, to))) {
l[u] = v;
r[v] = u;
return true;
}
}
return false;
};
for (int u : active)
if (l[u] == -1 && dfs(dfs, u)) ++ans;
}
}
};
} // namespace noya
#endif // NOYA_BIPARTITE_MATCHING_HPP
/// @complexity Time: O(V + E sqrt(V)) sparse;
/// O(V + W + N1 * (N1 * W + N2)) dense, with W words per row.
/// Space: O(V + E) sparse; O(V + W) dense auxiliary plus O(N1 * W) adjacency.
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
namespace noya {
namespace bipartite_matching_internal {
// GNU bitset and noya::dynamic_bitset have different find-next conventions.
// Other bitsets (including libc++ std::bitset) use a portable bitwise scan.
// For that fallback, replace W by the row's bit capacity in the time bound.
// dynamic_bitset is supplied by noya/ds/dynamic_bitset.hpp when needed.
template <class BS> std::size_t first(const BS &bits) {
if constexpr (requires { bits._Find_first(); }) return bits._Find_first();
else if constexpr (requires { bits.find_first(); }) return bits.find_first();
else {
for (std::size_t i = 0; i < bits.size(); ++i) if (bits[i]) return i;
return bits.size();
}
}
template <class BS> std::size_t next(const BS &bits, std::size_t pos) {
if constexpr (requires { bits._Find_next(pos); }) return bits._Find_next(pos);
else if constexpr (requires { bits.find_next(pos); }) return bits.find_next(pos + 1);
else {
for (++pos; pos < bits.size(); ++pos) if (bits[pos]) return pos;
return bits.size();
}
}
} // namespace bipartite_matching_internal
/// @brief Dense bipartite matching with bitset augmenting paths. Adjacency is
/// borrowed and unchanged; it must outlive this object. The first N1 rows have
/// equal capacities >= N2. Bits at positions >= N2 are ignored.
/// Supports GNU/libc++ std::bitset and noya::dynamic_bitset; only GNU and the
/// dynamic bitset provide word-efficient set-bit search.
template <typename BS> struct BipartiteMatching_Dense {
int N1, N2;
std::vector<BS> &adj;
std::vector<int> m1, m2, que, pre;
BS vis;
BipartiteMatching_Dense(std::vector<BS> &adj_, int n, int m)
: N1(n), N2(m), adj(adj_), m1(n, -1), m2(m, -1),
vis(adj_.empty() ? BS{} : adj_.front()) {
assert(n >= 0 && m >= 0 && adj.size() >= std::size_t(n));
for (int u = 0; u < n; ++u)
assert(adj[u].size() == vis.size() && adj[u].size() >= std::size_t(m));
using bipartite_matching_internal::first;
BS free = vis;
free.set();
std::vector<int> pending;
int count = 0, target = std::min(n, m);
for (int u = 0; u < n && count < target; ++u) {
if (first(adj[u]) >= std::size_t(m)) continue;
BS can = adj[u] & free;
std::size_t v = first(can);
if (v < std::size_t(m)) {
m1[u] = int(v);
m2[v] = u;
free.reset(v);
++count;
} else {
pending.push_back(u);
}
}
BS available = vis;
available.set();
for (int s : pending) {
if (count == target) break;
count += augment(s, available);
}
}
/// @brief Try one augmentation from an unmatched left vertex. After adding
/// edges, call this for every unmatched left vertex to restore maximal size.
/// The current matching must remain valid; graph dimensions cannot change.
void bfs(int s) {
assert(0 <= s && s < N1);
if (m1[s] != -1) return;
BS available = vis;
available.set(); // Do not reuse failed-search pruning after graph edits.
augment(s, available);
}
/// @brief Return matched pairs in increasing left-vertex order.
std::vector<std::pair<int, int>> matching() const {
std::vector<std::pair<int, int>> result;
for (int u = 0; u < N1; ++u)
if (m1[u] != -1) result.emplace_back(u, m1[u]);
return result;
}
/// @brief Minimum vertex cover as two increasing vertex lists. Requires a
/// maximum matching; does not change matching arrays or input adjacency.
std::pair<std::vector<int>, std::vector<int>> vertex_cover() {
using namespace bipartite_matching_internal;
std::vector<int> queue;
std::vector<bool> reached(N1);
for (int u = 0; u < N1; ++u)
if (m1[u] == -1) { reached[u] = true; queue.push_back(u); }
vis.set();
for (std::size_t head = 0; head < queue.size(); ++head) {
BS can = adj[queue[head]] & vis;
for (std::size_t v = first(can); v < std::size_t(N2); v = next(can, v)) {
vis.reset(v);
int u = m2[v];
assert(u != -1);
if (!reached[u]) { reached[u] = true; queue.push_back(u); }
}
}
std::vector<int> left, right;
for (int u = 0; u < N1; ++u) if (!reached[u]) left.push_back(u);
for (int v = 0; v < N2; ++v)
if (m2[v] != -1 && reached[m2[v]]) right.push_back(v);
return {std::move(left), std::move(right)};
}
private:
bool augment(int s, BS &available) {
using namespace bipartite_matching_internal;
que.resize(N1);
pre.resize(N1);
vis = available;
pre[s] = -1;
int head = 0, tail = 0;
que[tail++] = s;
while (head < tail) {
int u = que[head++];
BS can = adj[u] & vis;
for (std::size_t v = first(can); v < std::size_t(N2); v = next(can, v)) {
vis.reset(v);
if (m2[v] != -1) {
int to = m2[v];
que[tail++] = to;
pre[to] = u;
continue;
}
int a = u, b = int(v);
while (a != -1) {
int previous = m1[a];
m1[a] = b;
m2[b] = a;
a = pre[a];
b = previous;
}
return true;
}
}
// The failed reachable region is closed and has no free right vertex.
// Later augmentations cannot enter and leave it, so it stays unusable
// while this constructor's graph is fixed. Keep it excluded across roots.
available = vis;
return false;
}
};
/// @brief Maximum bipartite matching; l/r contain partners or -1, ans is its
/// size. Duplicate edges are allowed. Input order is preserved, unlike the old
/// shuffled implementation; the optimal witness is not canonical.
struct HopcroftKarp {
std::vector<int> g, l, r;
int ans = 0;
HopcroftKarp(int n, int m, const std::vector<std::pair<int, int>> &edges)
: g(edges.size()), l(n, -1), r(m, -1) {
assert(n >= 0 && m >= 0);
std::vector<std::size_t> off(std::size_t(n) + 1);
for (auto [u, v] : edges) {
assert(0 <= u && u < n && 0 <= v && v < m);
++off[u + 1];
}
for (int u = 0; u < n; ++u) off[u + 1] += off[u];
auto cur = off;
for (auto [u, v] : edges) g[cur[u]++] = v;
std::vector<int> active;
for (int u = 0; u < n; ++u) {
if (off[u] == off[u + 1]) continue;
active.push_back(u);
for (std::size_t i = off[u]; i < off[u + 1]; ++i) {
int v = g[i];
if (r[v] == -1) { l[u] = v; r[v] = u; ++ans; break; }
}
}
int target = std::min(int(active.size()), m);
if (ans == target) return;
std::vector<int> dist(n, -1), queue;
queue.reserve(active.size());
while (ans < target) {
for (int u : active) dist[u] = -1;
queue.clear();
for (int u : active)
if (l[u] == -1) { dist[u] = 0; queue.push_back(u); }
bool found = false;
for (std::size_t head = 0; head < queue.size(); ++head) {
int u = queue[head];
for (std::size_t i = off[u]; i < off[u + 1]; ++i) {
int to = r[g[i]];
if (to == -1) found = true;
else if (dist[to] == -1) {
dist[to] = dist[u] + 1;
queue.push_back(to);
}
}
}
if (!found) break;
// Consume each left vertex once per phase, including successful paths.
auto dfs = [&](auto &self, int u) -> bool {
int depth = dist[u];
dist[u] = -1;
for (auto i = off[u]; i < off[u + 1]; ++i) {
int v = g[i], to = r[v];
if (to == -1 || (dist[to] == depth + 1 && self(self, to))) {
l[u] = v;
r[v] = u;
return true;
}
}
return false;
};
for (int u : active)
if (l[u] == -1 && dfs(dfs, u)) ++ans;
}
}
};
} // namespace noya
// NOYA_BIPARTITE_MATCHING_HPP