C++ Library for Competitive Programming
#include "emthrm/graph/flow/matching/weighted_bipartite_matching.hpp"
互いに端点を共有しない辺集合である。
任意の頂点がいずれかの端点となっている辺集合である。
互いに隣接していない頂点集合である。
任意の辺に対して少なくとも一方の端点を含む頂点集合である。
無向グラフに対して完全グラフな部分グラフである。
孤立点のないグラフに対して (最大マッチングのサイズ) + (最小辺被覆のサイズ) = (頂点数) が成り立つ。
(最大独立集合のサイズ) + (最小頂点被覆のサイズ) = (頂点数)
二部グラフ $(U, V, E)$ に対して $\lvert U \rvert = \lvert V \rvert \implies (\text{完全二部マッチングの個数}) \equiv \lvert A \rvert \pmod{2}$ が成り立つ。ただし $A$ は $a_{ij} = \begin{cases} 1 & (\lbrace U_i, V_j \rbrace \in E), \\ 0 & (\text{otherwise}) \end{cases}$ を満たす $\lvert U \rvert \times \lvert V \rvert$ 型行列である。
二部グラフに対して、最大マッチングのサイズは最小頂点被覆のサイズに等しい。
有向非巡回グラフの最小パス被覆は二部グラフの最大マッチングに帰着できる。
二部グラフ $(U, V, E)$ に対して、以下は同値である。
任意の有限な半順序集合に対して、反鎖 (antichain) の最大サイズは共通部分のない鎖 (chain) に分解したときの最小サイズに等しい。
特に有向非巡回グラフ $G$ では、$\forall u, v \in V(G)$ に対して
\[u \leq v \iff u \text{ から } v \text{ に到達可能である。}\]と定義すると、$(V(G), \leq)$ は半順序集合である。$(V(G), \leq)$ に対して、共通部分のない鎖に分解したときの最小サイズは最小パス被覆のサイズを意味する。
時間計算量 | |
---|---|
二部グラフの最大マッチング | $O(\lvert V \rvert \lvert E \rvert)$ |
Hopcroft–Karp algorithm | $O(\lvert E \rvert \sqrt{\lvert V \rvert})$ |
二部グラフの重み付き最大マッチング | $O(\lvert E \rvert \lvert V \rvert \log{\lvert V \rvert})$ |
一般グラフの最大マッチング | $O({\lvert V \rvert}^3 + \lvert E \rvert)$ |
struct BipartiteMatching;
名前 | 説明 |
---|---|
std::vector<int> match |
マッチした相手。ただし存在しないときは $-1$ となる。 |
名前 | 効果・戻り値 |
---|---|
explicit BipartiteMatching(const int n); |
頂点数 $N$ のオブジェクトを構築する。 |
void add_edge(const int u, const int v); |
辺 $(u, v)$ を加える。 |
int solve(); |
最大マッチングのサイズ |
void fix(const int ver); |
頂点 $\mathrm{ver}$ に対するマッチングを固定する。 |
int activate(const int ver); |
頂点 $\mathrm{ver}$ を有効にしたのち、最大マッチングのサイズの変化量を返す。 |
int deactivate(const int ver); |
頂点 $\mathrm{ver}$ を無効にしたのち、最大マッチングのサイズの変化量を返す。 |
struct HopcroftKarp;
名前 | 説明 |
---|---|
std::vector<int> match |
マッチした相手。ただし存在しないときは $-1$ となる。 |
名前 | 効果・戻り値 |
---|---|
explicit HopcroftKarp(const int left, const int right); |
頂点数 $\mathrm{left}$ と $\mathrm{right}$ の二部グラフに対してオブジェクトを構築する。 |
void add_edge(const int u, const int v); |
辺 $(u, v)$ を加える。 |
int solve(); |
最大マッチングのサイズ |
template <typename T>
struct WeightedBipartiteMatching;
T
:重みを表す型名前 | 効果・戻り値 | |
---|---|---|
explicit WeightedBipartiteMatching(const int left, const int right); |
頂点数 $\mathrm{left}$ と $\mathrm{right}$ の二部グラフに対してオブジェクトを構築する。 | |
void add_edge(const int src, const int dst, const T cost); |
重み $\mathrm{cost}$ の辺 $(\mathrm{src}, \mathrm{dst})$ を加える。 | |
T solve(); |
重み付き最大マッチングの重み | |
std::vector<int> matching() const; |
マッチした相手。ただし存在しないときは $-1$ が格納される。 |
名前 | 戻り値 |
---|---|
int maximum_matching(const std::vector<std::vector<int>>& graph); |
無向グラフ $\mathrm{graph}$ の最大マッチングのサイズ |
性質3
性質5・Dilworth’s theorem
Hall’s theorem
二部グラフの最大マッチング
Hopcroft–Karp algorithm
二部グラフの重み付き最大マッチング
一般グラフの最大マッチング
#ifndef EMTHRM_GRAPH_FLOW_MATCHING_WEIGHTED_BIPARTITE_MATCHING_HPP_
#define EMTHRM_GRAPH_FLOW_MATCHING_WEIGHTED_BIPARTITE_MATCHING_HPP_
#include <cassert>
#include <vector>
#include "emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp"
namespace emthrm {
template <typename T>
struct WeightedBipartiteMatching {
explicit WeightedBipartiteMatching(const int left, const int right)
: is_built(false), left(left), right(right), mcf(left + right + 2) {}
void add_edge(const int src, const int dst, const T cost) {
mcf.add_edge(src, left + dst, 1, -cost);
}
T solve() {
assert(!is_built);
is_built = true;
const int s = left + right, t = left + right + 1;
for (int i = 0; i < left; ++i) {
mcf.add_edge(s, i, 1, 0);
}
for (int i = 0; i < right; ++i) {
mcf.add_edge(left + i, t, 1, 0);
}
return -mcf.minimum_cost_maximum_flow(s, t, left).second;
}
std::vector<int> matching() const {
assert(is_built);
std::vector<int> res(left, -1);
for (int i = 0; i < left; ++i) {
for (const auto& e : mcf.graph[i]) {
if (e.cap == 0 && left <= e.dst && e.dst < left + right) {
res[i] = e.dst - left;
break;
}
}
}
return res;
}
private:
bool is_built;
const int left, right;
MinimumCostSTFlow<int, T> mcf;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_FLOW_MATCHING_WEIGHTED_BIPARTITE_MATCHING_HPP_
#line 1 "include/emthrm/graph/flow/matching/weighted_bipartite_matching.hpp"
#include <cassert>
#include <vector>
#line 1 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp"
#include <algorithm>
#line 6 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp"
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#line 11 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp"
namespace emthrm {
template <typename T, typename U>
struct MinimumCostSTFlow {
struct Edge {
int dst, rev;
T cap;
U cost;
explicit Edge(const int dst, const T cap, const U cost, const int rev)
: dst(dst), rev(rev), cap(cap), cost(cost) {}
};
const U uinf;
std::vector<std::vector<Edge>> graph;
explicit MinimumCostSTFlow(const int n,
const U uinf = std::numeric_limits<U>::max())
: uinf(uinf), graph(n), tinf(std::numeric_limits<T>::max()), n(n),
has_negative_edge(false), prev_v(n, -1), prev_e(n, -1), dist(n),
potential(n, 0) {}
void add_edge(const int src, const int dst, const T cap, const U cost) {
has_negative_edge |= cost < 0;
graph[src].emplace_back(dst, cap, cost, graph[dst].size());
graph[dst].emplace_back(src, 0, -cost, graph[src].size() - 1);
}
U solve(const int s, const int t, T flow) {
if (flow == 0) [[unlikely]] return 0;
U res = 0;
has_negative_edge ? bellman_ford(s) : dijkstra(s);
while (true) {
if (dist[t] == uinf) return uinf;
res += calc(s, t, &flow);
if (flow == 0) break;
dijkstra(s);
}
return res;
}
U solve(const int s, const int t) {
U res = 0;
T flow = tinf;
bellman_ford(s);
while (potential[t] < 0 && dist[t] != uinf) {
res += calc(s, t, &flow);
dijkstra(s);
}
return res;
}
std::pair<T, U> minimum_cost_maximum_flow(const int s, const int t,
const T flow) {
if (flow == 0) [[unlikely]] return {0, 0};
T f = flow;
U cost = 0;
has_negative_edge ? bellman_ford(s) : dijkstra(s);
while (dist[t] != uinf) {
cost += calc(s, t, &f);
if (f == 0) break;
dijkstra(s);
}
return {flow - f, cost};
}
private:
const T tinf;
const int n;
bool has_negative_edge;
std::vector<int> prev_v, prev_e;
std::vector<U> dist, potential;
std::priority_queue<std::pair<U, int>, std::vector<std::pair<U, int>>,
std::greater<std::pair<U, int>>> que;
void bellman_ford(const int s) {
std::fill(dist.begin(), dist.end(), uinf);
dist[s] = 0;
bool is_updated = true;
for (int step = 0; step < n && is_updated; ++step) {
is_updated = false;
for (int i = 0; i < n; ++i) {
if (dist[i] == uinf) continue;
for (int j = 0; std::cmp_less(j, graph[i].size()); ++j) {
const Edge& e = graph[i][j];
if (e.cap > 0 && dist[e.dst] > dist[i] + e.cost) {
dist[e.dst] = dist[i] + e.cost;
prev_v[e.dst] = i;
prev_e[e.dst] = j;
is_updated = true;
}
}
}
}
assert(!is_updated);
for (int i = 0; i < n; ++i) {
if (dist[i] != uinf) potential[i] += dist[i];
}
}
void dijkstra(const int s) {
std::fill(dist.begin(), dist.end(), uinf);
dist[s] = 0;
que.emplace(0, s);
while (!que.empty()) {
const auto [d, ver] = que.top();
que.pop();
if (dist[ver] < d) continue;
for (int i = 0; std::cmp_less(i, graph[ver].size()); ++i) {
const Edge& e = graph[ver][i];
const U nxt = dist[ver] + e.cost + potential[ver] - potential[e.dst];
if (e.cap > 0 && dist[e.dst] > nxt) {
dist[e.dst] = nxt;
prev_v[e.dst] = ver;
prev_e[e.dst] = i;
que.emplace(dist[e.dst], e.dst);
}
}
}
for (int i = 0; i < n; ++i) {
if (dist[i] != uinf) potential[i] += dist[i];
}
}
U calc(const int s, const int t, T* flow) {
T f = *flow;
for (int v = t; v != s; v = prev_v[v]) {
f = std::min(f, graph[prev_v[v]][prev_e[v]].cap);
}
*flow -= f;
for (int v = t; v != s; v = prev_v[v]) {
Edge& e = graph[prev_v[v]][prev_e[v]];
e.cap -= f;
graph[v][e.rev].cap += f;
}
return potential[t] * f;
}
};
} // namespace emthrm
#line 8 "include/emthrm/graph/flow/matching/weighted_bipartite_matching.hpp"
namespace emthrm {
template <typename T>
struct WeightedBipartiteMatching {
explicit WeightedBipartiteMatching(const int left, const int right)
: is_built(false), left(left), right(right), mcf(left + right + 2) {}
void add_edge(const int src, const int dst, const T cost) {
mcf.add_edge(src, left + dst, 1, -cost);
}
T solve() {
assert(!is_built);
is_built = true;
const int s = left + right, t = left + right + 1;
for (int i = 0; i < left; ++i) {
mcf.add_edge(s, i, 1, 0);
}
for (int i = 0; i < right; ++i) {
mcf.add_edge(left + i, t, 1, 0);
}
return -mcf.minimum_cost_maximum_flow(s, t, left).second;
}
std::vector<int> matching() const {
assert(is_built);
std::vector<int> res(left, -1);
for (int i = 0; i < left; ++i) {
for (const auto& e : mcf.graph[i]) {
if (e.cap == 0 && left <= e.dst && e.dst < left + right) {
res[i] = e.dst - left;
break;
}
}
}
return res;
}
private:
bool is_built;
const int left, right;
MinimumCostSTFlow<int, T> mcf;
};
} // namespace emthrm