This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../../src/template/template.hpp"
#include "../../../src/graph/graph_template.hpp"
#include "../../../src/graph/max_matching.hpp"
int brute_max_matching(const int n, const vector<pair<int, int>>& es) {
const int m = es.size();
int res = 0;
for(int bit = 0; bit < (1 << m); ++bit) {
vector<int> used(n, false);
int cnt = 0;
bool ok = true;
for(int i = 0; i < m; ++i) {
if(!(bit >> i & 1)) continue;
const auto& [u, v] = es[i];
if(used[u] or used[v]) {
ok = false;
break;
}
used[u] = used[v] = true;
++cnt;
}
if(ok) res = max(res, cnt);
}
return res;
}
int main() {
int a, b;
cin >> a >> b;
cout << a + b << '\n';
mt19937 rng(12345);
rep(n, 1, 9) {
vector<pair<int, int>> all_edges;
rep(i, 0, n) rep(j, i + 1, n) all_edges.emplace_back(i, j);
rep(_, 0, 200) {
Edges<int> input;
vector<pair<int, int>> es;
for(const auto& [u, v] : all_edges) {
if((rng() & 1) == 0) continue;
input.emplace_back(u, v, 1);
es.emplace_back(u, v);
}
const auto got = max_matching(n, input);
assert((int)got.size() == brute_max_matching(n, es));
vector<int> used(n, false);
for(const auto& e : got) {
assert(0 <= e.from and e.from < n);
assert(0 <= e.to and e.to < n);
assert(!used[e.from]);
assert(!used[e.to]);
used[e.from] = used[e.to] = true;
}
}
}
}#line 1 "verify/unit_test/graph/max_matching.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
#line 4 "src/template/template.hpp"
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
SetupIO() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(30);
}
} setup_io;
#line 3 "src/graph/graph_template.hpp"
template <typename T>
struct Edge {
int from, to;
T cost;
int idx;
Edge()
: from(-1), to(-1), cost(-1), idx(-1) {}
Edge(const int from, const int to, const T& cost = 1, const int idx = -1)
: from(from), to(to), cost(cost), idx(idx) {}
operator int() const {
return to;
}
};
template <typename T>
struct Graph {
Graph(const int N)
: n(N), es(0), g(N) {}
int size() const {
return n;
}
int edge_size() const {
return es;
}
void add_edge(const int from, const int to, const T& cost = 1) {
assert(0 <= from and from < n);
assert(0 <= to and to < n);
g[from].emplace_back(from, to, cost, es);
g[to].emplace_back(to, from, cost, es++);
}
void add_directed_edge(const int from, const int to, const T& cost = 1) {
assert(0 <= from and from < n);
assert(0 <= to and to < n);
g[from].emplace_back(from, to, cost, es++);
}
inline vector<Edge<T>>& operator[](const int& k) {
assert(0 <= k and k < n);
return g[k];
}
inline const vector<Edge<T>>& operator[](const int& k) const {
assert(0 <= k and k < n);
return g[k];
}
private:
int n, es;
vector<vector<Edge<T>>> g;
};
template <typename T>
using Edges = vector<Edge<T>>;
#line 4 "src/graph/max_matching.hpp"
template <typename T>
Edges<T> max_matching(const int n, const Edges<T>& es) {
struct GabowEdmonds {
struct AdjEdge {
int to, id;
};
int n, offset;
vector<vector<AdjEdge>> g;
vector<pair<int, int>> edges;
vector<int> mate, label, first, que;
GabowEdmonds(const int n)
: n(n), offset(n + 1), g(n + 1), mate(n + 1), label(n + 1, -1), first(n + 1) {
que.reserve(n + 1);
}
void add_edge(int u, int v) {
++u;
++v;
const int id = offset + (int)edges.size();
g[u].push_back({v, id});
g[v].push_back({u, id});
edges.emplace_back(u, v);
}
int find(const int v) {
if(label[first[v]] < 0) return first[v];
return first[v] = find(first[v]);
}
void rematch(const int v, const int w) {
const int t = mate[v];
mate[v] = w;
if(mate[t] != v) return;
if(label[v] < offset) {
mate[t] = label[v];
rematch(label[v], t);
} else {
const auto& [x, y] = edges[label[v] - offset];
rematch(x, y);
rematch(y, x);
}
}
void assign_label(const int x, const int y, const int id) {
int r = find(x), s = find(y);
if(r == s) return;
int join = 0;
label[r] = label[s] = -id;
while(true) {
if(s != 0) swap(r, s);
r = find(label[mate[r]]);
if(label[r] == -id) {
join = r;
break;
}
label[r] = -id;
}
int v = first[x];
while(v != join) {
que.push_back(v);
label[v] = id;
first[v] = join;
v = first[label[mate[v]]];
}
v = first[y];
while(v != join) {
que.push_back(v);
label[v] = id;
first[v] = join;
v = first[label[mate[v]]];
}
}
bool augment(const int root) {
int head = 0;
que.clear();
first[root] = 0;
label[root] = 0;
que.push_back(root);
while(head < (int)que.size()) {
const int v = que[head++];
for(const AdjEdge& e : g[v]) {
const int u = e.to;
if(mate[u] == 0 and u != root) {
mate[u] = v;
rematch(v, u);
return true;
}
if(label[u] >= 0) {
assign_label(v, u, e.id);
} else if(label[mate[u]] < 0) {
label[mate[u]] = v;
first[mate[u]] = u;
que.push_back(mate[u]);
}
}
}
return false;
}
vector<pair<int, int>> solve() {
for(int i = 1; i <= n; ++i) {
if(mate[i] != 0) continue;
if(augment(i)) fill(label.begin(), label.end(), -1);
}
vector<pair<int, int>> res;
res.reserve(n / 2);
for(int i = 1; i <= n; ++i) {
if(i < mate[i]) res.emplace_back(i - 1, mate[i] - 1);
}
return res;
}
};
GabowEdmonds matching(n);
vector<int> deg(n);
for(const Edge<T>& e : es) {
assert(e.cost == 1);
assert(0 <= e.from and e.from < n);
assert(0 <= e.to and e.to < n);
if(e.from == e.to) continue;
++deg[e.from];
++deg[e.to];
}
for(int i = 0; i < n; ++i) {
matching.g[i + 1].reserve(deg[i]);
}
for(const Edge<T>& e : es) {
if(e.from != e.to) matching.add_edge(e.from, e.to);
}
const vector<pair<int, int>> pairs = matching.solve();
Edges<T> res;
res.reserve(pairs.size());
for(const auto& [u, v] : pairs) {
res.emplace_back(u, v, T(1));
}
return res;
}
#line 5 "verify/unit_test/graph/max_matching.test.cpp"
int brute_max_matching(const int n, const vector<pair<int, int>>& es) {
const int m = es.size();
int res = 0;
for(int bit = 0; bit < (1 << m); ++bit) {
vector<int> used(n, false);
int cnt = 0;
bool ok = true;
for(int i = 0; i < m; ++i) {
if(!(bit >> i & 1)) continue;
const auto& [u, v] = es[i];
if(used[u] or used[v]) {
ok = false;
break;
}
used[u] = used[v] = true;
++cnt;
}
if(ok) res = max(res, cnt);
}
return res;
}
int main() {
int a, b;
cin >> a >> b;
cout << a + b << '\n';
mt19937 rng(12345);
rep(n, 1, 9) {
vector<pair<int, int>> all_edges;
rep(i, 0, n) rep(j, i + 1, n) all_edges.emplace_back(i, j);
rep(_, 0, 200) {
Edges<int> input;
vector<pair<int, int>> es;
for(const auto& [u, v] : all_edges) {
if((rng() & 1) == 0) continue;
input.emplace_back(u, v, 1);
es.emplace_back(u, v);
}
const auto got = max_matching(n, input);
assert((int)got.size() == brute_max_matching(n, es));
vector<int> used(n, false);
for(const auto& e : got) {
assert(0 <= e.from and e.from < n);
assert(0 <= e.to and e.to < n);
assert(!used[e.from]);
assert(!used[e.to]);
used[e.from] = used[e.to] = true;
}
}
}
}