proconlib
This documentation is automatically generated by online-judge-tools/verification-helper
test/bipartite_matching.test.cpp
- View this file on GitHub
- Last update: 2022-03-31 10:32:23+09:00
- Problem: https://judge.yosupo.jp/problem/bipartitematching
Depends on
- graph/dinic.cpp
- internal/simple_queue.cpp
- utility/index_offset.cpp
- utility/rec_lambda.cpp
- utility/rep.cpp
Code
#define PROBLEM "https://judge.yosupo.jp/problem/bipartitematching"
#include "../utility/rep.cpp"
#include "../graph/dinic.cpp"
#include <iostream>
#include <vector>
int main() {
int L, R, M;
std::cin >> L >> R >> M;
Dinic<int> dinic;
const auto src = dinic.add_vertex();
const auto dst = dinic.add_vertex();
const auto left = dinic.add_vertices(L);
const auto right = dinic.add_vertices(R);
std::vector<int> eidx(M);
for (const auto i : rep(0, L)) {
dinic.add_edge(src, left[i], 1);
}
for (const auto i : rep(0, R)) {
dinic.add_edge(right[i], dst, 1);
}
for (const auto i : rep(0, M)) {
int a, b;
std::cin >> a >> b;
eidx[i] = dinic.add_edge(left[a], right[b], 1);
}
std::cout << dinic.flow(src, dst) << '\n';
for (const auto i : rep(0, M)) {
const auto& [src, dst, flow, _] = dinic.get_edge(eidx[i]);
if (flow == 1) {
std::cout << left.to_idx(src) << ' ' << right.to_idx(dst) << '\n';
}
}
return 0;
}#line 1 "test/bipartite_matching.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/bipartitematching"
#line 2 "utility/rep.cpp"
#include <algorithm>
class Range {
struct Iter {
int itr;
constexpr Iter(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { ++itr; }
constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
constexpr int operator*() const noexcept { return itr; }
};
const Iter first, last;
public:
explicit constexpr Range(const int first, const int last) noexcept : first(first), last(std::max(first, last)) {}
constexpr Iter begin() const noexcept { return first; }
constexpr Iter end() const noexcept { return last; }
};
constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); }
constexpr Range rep(const int n) noexcept { return Range(0, n); }
#line 3 "graph/dinic.cpp"
#include <cassert>
#include <limits>
#include <type_traits>
#include <vector>
#line 3 "internal/simple_queue.cpp"
namespace proconlib {
template <class T> class SimpleQueue {
std::vector<T> payload;
int pos;
public:
SimpleQueue() : payload(), pos(0) {}
explicit SimpleQueue(const int n) : SimpleQueue() { reserve(n); }
int size() const { return (int)payload.size() - pos; }
bool empty() const { return size() == 0; }
T& front() { return payload[pos]; }
void push(const T& t) { payload.push_back(t); }
void push(T&& t) { payload.push_back(std::move(t)); }
void pop() { pos++; }
void reserve(int n) { payload.reserve(n); }
void clear() {
payload.clear();
pos = 0;
}
};
} // namespace proconlib
#line 3 "utility/index_offset.cpp"
class IndexOffset {
int offset, len;
public:
constexpr IndexOffset() noexcept : offset(), len() {}
explicit constexpr IndexOffset(const int o, const int l) noexcept : offset(o), len(l) {}
constexpr int size() const { return len; }
constexpr int operator[](const int i) const noexcept {
assert(i < len);
return offset + i;
}
constexpr int to_idx(const int i) const noexcept {
assert(offset <= i and i < offset + len);
return i - offset;
}
};
#line 3 "utility/rec_lambda.cpp"
#include <utility>
template <class F> struct RecursiveLambda : private F {
explicit constexpr RecursiveLambda(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template <class F> constexpr decltype(auto) rec_lambda(F&& f) { return RecursiveLambda<F>(std::forward<F>(f)); }
#line 11 "graph/dinic.cpp"
template <class Flow, std::enable_if_t<std::is_integral_v<Flow>>* = nullptr> class Dinic {
public:
struct Edge {
int src, dst;
Flow flow, cap;
};
private:
int node_count;
std::vector<Edge> graph;
public:
Dinic() : node_count(0), graph() {}
explicit Dinic(const int n) : node_count(n), graph() {}
int size() const { return node_count; }
int edge_count() const { return graph.size(); }
int add_vertex() { return node_count++; }
IndexOffset add_vertices(const int n) {
assert(n >= 0);
const IndexOffset ret(size(), n);
node_count += n;
return ret;
}
const Edge& get_edge(const int i) const {
assert(0 <= i and i < edge_count());
return graph[i];
}
int add_edge(const int src, const int dst, const Flow& cap) {
assert(0 <= src and src < size());
assert(0 <= dst and dst < size());
assert(cap >= 0);
graph.push_back(Edge{src, dst, 0, cap});
return edge_count() - 1;
}
Flow flow(const int src, const int dst) { return flow(src, dst, std::numeric_limits<Flow>::max()); }
Flow flow(const int src, const int dst, const Flow& flow_limit) {
assert(0 <= src and src < size());
assert(0 <= dst and dst < size());
assert(src != dst);
const int n = size();
const int m = edge_count();
struct E {
int dst, rev;
Flow cap;
};
std::vector<E> edge(2 * m);
std::vector<int> start(n + 1), eidx(m);
{
std::vector<int> deg(n), reidx(m);
for (const int i : rep(m)) {
eidx[i] = deg[graph[i].src]++;
reidx[i] = deg[graph[i].dst]++;
}
for (const int i : rep(n)) start[i + 1] = start[i] + deg[i];
for (const int i : rep(m)) {
const auto& e = graph[i];
const int u = e.src, v = e.dst;
eidx[i] += start[u];
reidx[i] += start[v];
edge[eidx[i]] = {v, reidx[i], e.cap - e.flow};
edge[reidx[i]] = {u, eidx[i], e.flow};
}
}
std::vector<int> level(n), iter(n);
proconlib::SimpleQueue<int> que;
const auto bfs = [&] {
std::fill(level.begin(), level.end(), n);
level[src] = 0;
while (!que.empty()) que.pop();
que.push(src);
while (!que.empty()) {
const int u = que.front();
que.pop();
for (const int i : rep(start[u], start[u + 1])) {
const auto& e = edge[i];
if (e.cap == 0 or level[e.dst] < n) continue;
level[e.dst] = level[u] + 1;
if (e.dst == dst) return;
que.push(e.dst);
}
}
};
const auto dfs = rec_lambda([&](auto&& dfs, const int u, const Flow& ub) -> Flow {
if (u == src) return ub;
Flow ret = 0;
for (int& i = iter[u]; i < start[u + 1]; i += 1) {
auto& e = edge[i];
auto& re = edge[e.rev];
if (level[u] <= level[e.dst] or re.cap == 0) continue;
const Flow d = dfs(e.dst, std::min(ub - ret, re.cap));
if (d == 0) continue;
e.cap += d;
re.cap -= d;
ret += d;
if (ret == ub) return ret;
}
level[u] = n;
return ret;
});
Flow ret = 0;
while (ret < flow_limit) {
bfs();
if (level[dst] == n) break;
std::copy(start.begin(), start.begin() + n, iter.begin());
const Flow f = dfs(dst, flow_limit - ret);
if (f == 0) break;
ret += f;
}
for (const int i : rep(m)) graph[i].flow = graph[i].cap - edge[eidx[i]].cap;
return ret;
}
std::vector<char> min_cut(const int src) const {
assert(0 <= src and src < size());
const int n = size();
std::vector<std::vector<int>> adj(n);
for (const auto& e : graph) {
if (e.flow < e.cap) adj[e.src].push_back(e.dst);
if (e.flow > 0) adj[e.dst].push_back(e.src);
}
std::vector<char> ret(n);
proconlib::SimpleQueue<int> que;
que.push(src);
ret[src] = true;
while (!que.empty()) {
const int u = que.front();
que.pop();
for (const int v : adj[u]) {
if (!ret[v]) {
ret[v] = true;
que.push(v);
}
}
}
return ret;
}
};
#line 4 "test/bipartite_matching.test.cpp"
#include <iostream>
#line 6 "test/bipartite_matching.test.cpp"
int main() {
int L, R, M;
std::cin >> L >> R >> M;
Dinic<int> dinic;
const auto src = dinic.add_vertex();
const auto dst = dinic.add_vertex();
const auto left = dinic.add_vertices(L);
const auto right = dinic.add_vertices(R);
std::vector<int> eidx(M);
for (const auto i : rep(0, L)) {
dinic.add_edge(src, left[i], 1);
}
for (const auto i : rep(0, R)) {
dinic.add_edge(right[i], dst, 1);
}
for (const auto i : rep(0, M)) {
int a, b;
std::cin >> a >> b;
eidx[i] = dinic.add_edge(left[a], right[b], 1);
}
std::cout << dinic.flow(src, dst) << '\n';
for (const auto i : rep(0, M)) {
const auto& [src, dst, flow, _] = dinic.get_edge(eidx[i]);
if (flow == 1) {
std::cout << left.to_idx(src) << ' ' << right.to_idx(dst) << '\n';
}
}
return 0;
}