#line 1 "test/aoj/GRL_7_A/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A"
#include <iostream>
#line 2 "Mylib/Graph/Flow/ford_fulkerson.cpp"
#include <algorithm>
#include <cassert>
#include <vector>
namespace haar_lib {
namespace ford_fulkerson_impl {
template <typename T>
struct edge {
int from, to, rev;
T cap;
bool is_rev;
edge(int from, int to, int rev, T cap, bool is_rev) : from(from), to(to), rev(rev), cap(cap), is_rev(is_rev) {}
};
} // namespace ford_fulkerson_impl
template <typename T>
class ford_fulkerson {
public:
using edge = ford_fulkerson_impl::edge<T>;
using capacity_type = T;
private:
int size_;
std::vector<std::vector<edge>> g_;
std::vector<bool> visit_;
T dfs(int from, int to, T flow) {
if (from == to) return flow;
visit_[from] = true;
for (auto &e : g_[from]) {
if (not visit_[e.to] and e.cap > 0) {
T d = dfs(e.to, to, std::min(flow, e.cap));
if (d > 0) {
e.cap -= d;
g_[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
public:
ford_fulkerson() {}
ford_fulkerson(int size) : size_(size), g_(size), visit_(size) {}
void add_edge(int from, int to, T c) {
assert(0 <= from and from < size_);
assert(0 <= to and to < size_);
g_[from].emplace_back(from, to, (int) g_[to].size(), c, false);
g_[to].emplace_back(to, from, (int) g_[from].size() - 1, 0, true);
}
void reset_flow() {
for (auto &v : g_) {
for (auto &e : v) {
if (e.is_rev) {
g_[e.to][e.rev].cap += e.cap;
e.cap = 0;
}
}
}
}
T max_flow(int s, int t) {
assert(0 <= s and s < size_);
assert(0 <= t and t < size_);
T ret = 0;
while (1) {
visit_.assign(size_, false);
T flow = dfs(s, t, std::numeric_limits<T>::max());
if (flow == 0) return ret;
ret += flow;
}
}
std::vector<edge> edges() const {
std::vector<edge> ret;
for (auto &v : g_) ret.insert(ret.end(), v.begin(), v.end());
return ret;
}
};
} // namespace haar_lib
#line 3 "Mylib/Graph/Matching/bipartite_matching.cpp"
#include <utility>
#line 5 "Mylib/Graph/Matching/bipartite_matching.cpp"
namespace haar_lib {
template <typename MaxFlow>
class bipartite_matching {
int L_, R_, s_, t_;
MaxFlow f_;
public:
bipartite_matching() {}
bipartite_matching(int L, int R) : L_(L), R_(R), s_(L + R), t_(s_ + 1), f_(L + R + 2) {
for (int i = 0; i < L_; ++i) f_.add_edge(s_, i, 1);
for (int i = 0; i < R_; ++i) f_.add_edge(L_ + i, t_, 1);
}
void add_edge(int i, int j) {
assert(0 <= i and i < L_ and 0 <= j and j < R_);
f_.add_edge(i, L_ + j, 1);
}
int match() {
return f_.max_flow(s_, t_);
}
auto get_matching() {
const auto g = f_.edges();
std::vector<std::pair<int, int>> ret;
for (auto &e : g) {
if (not e.is_rev and e.cap == 0 and e.from != s_ and e.to != t_) {
ret.emplace_back(e.from, e.to - L_);
}
}
return ret;
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples.cpp"
#include <tuple>
#line 6 "Mylib/IO/input_tuple.cpp"
namespace haar_lib {
template <typename T, size_t... I>
static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
}
template <typename T, typename U>
std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
s >> value.first >> value.second;
return s;
}
template <typename... Args>
std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
return s;
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuples {
struct iter {
using value_type = std::tuple<Args...>;
value_type value;
bool fetched = false;
int N, c = 0;
value_type operator*() {
if (not fetched) {
std::cin >> value;
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuples(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples(int N) {
return InputTuples<Args...>(N);
}
} // namespace haar_lib
#line 7 "test/aoj/GRL_7_A/main.test.cpp"
namespace hl = haar_lib;
int main() {
int X, Y, E;
std::cin >> X >> Y >> E;
hl::bipartite_matching<hl::ford_fulkerson<int>> b(X, Y);
for (auto [x, y] : hl::input_tuples<int, int>(E)) {
b.add_edge(x, y);
}
int ans = b.match();
std::cout << ans << std::endl;
return 0;
}
test/aoj/GRL_7_A/main.test.cpp
Ford-Fulkerson algorithm
(Mylib/Graph/Flow/ford_fulkerson.cpp)