#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2293"
#include <iostream>
#include <vector>
#include "Mylib/Graph/Flow/minimum_cost_flow.cpp"
#include "Mylib/Graph/Matching/weighted_bipartite_matching.cpp"
#include "Mylib/IO/input_tuple_vector.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int n;
std::cin >> n;
auto [A, B] = hl::input_tuple_vector<int, int>(n);
std::vector<int> ls(A);
ls.insert(ls.end(), B.begin(), B.end());
std::sort(ls.begin(), ls.end());
ls.erase(std::unique(ls.begin(), ls.end()), ls.end());
hl::weighted_bipartite_matching<int, hl::minimum_cost_flow<int, int>> m(n, ls.size(), true);
for (int i = 0; i < n; ++i) {
m.add_edge(i, std::lower_bound(ls.begin(), ls.end(), A[i]) - ls.begin(), B[i]);
m.add_edge(i, std::lower_bound(ls.begin(), ls.end(), B[i]) - ls.begin(), A[i]);
}
int ans = m.match(n);
std::cout << ans << std::endl;
return 0;
}
#line 1 "test/aoj/2293/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2293"
#include <iostream>
#include <vector>
#line 2 "Mylib/Graph/Flow/minimum_cost_flow.cpp"
#include <algorithm>
#include <cassert>
#include <functional>
#include <queue>
#include <tuple>
#include <utility>
#line 9 "Mylib/Graph/Flow/minimum_cost_flow.cpp"
namespace haar_lib {
namespace minimum_cost_flow_impl {
template <typename T, typename U>
struct edge {
int from, to, rev;
T cap;
U cost;
bool is_rev;
edge(int from, int to, int rev, T cap, U cost, bool is_rev) : from(from), to(to), rev(rev), cap(cap), cost(cost), is_rev(is_rev) {}
};
} // namespace minimum_cost_flow_impl
template <typename Capacity, typename Cost>
class minimum_cost_flow {
public:
using edge = minimum_cost_flow_impl::edge<Capacity, Cost>;
using capacity_type = Capacity;
using cost_type = Cost;
private:
int size_;
std::vector<std::vector<edge>> g_;
public:
minimum_cost_flow() {}
minimum_cost_flow(int size) : size_(size), g_(size) {}
void add_edge(int from, int to, Capacity cap, Cost cost) {
assert(0 <= from and from < size_);
assert(0 <= to and to < size_);
g_[from].emplace_back(from, to, g_[to].size(), cap, cost, false);
g_[to].emplace_back(to, from, g_[from].size() - 1, 0, -cost, true);
}
std::pair<Capacity, Cost> min_cost_flow(int src, int dst, const Capacity &f) {
assert(0 <= src and src < size_);
assert(0 <= dst and dst < size_);
using P = std::pair<Cost, int>;
Cost ret = 0;
Capacity flow = f;
std::vector<Cost> h(size_, 0), cost(size_);
std::vector<bool> is_inf(size_, true);
std::vector<int> prev_node(size_), prev_edge(size_);
std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
while (flow > 0) {
std::fill(is_inf.begin(), is_inf.end(), true);
// src -> dst の最小コスト経路を探索する。 (dijkstra algorithm)
cost[src] = 0;
pq.emplace(0, src);
is_inf[src] = false;
while (not pq.empty()) {
Cost c;
int v;
std::tie(c, v) = pq.top();
pq.pop();
if (cost[v] < c) continue;
for (int i = 0; i < (int) g_[v].size(); ++i) {
edge &e = g_[v][i];
int w = e.to;
Capacity cap = e.cap;
Cost cst = e.cost;
if (cap > 0) {
if (is_inf[w] or cost[w] + h[w] > cost[v] + h[v] + cst) {
is_inf[w] = false;
cost[w] = cost[v] + cst + h[v] - h[w];
prev_node[w] = v;
prev_edge[w] = i;
pq.emplace(cost[w], w);
}
}
}
}
if (is_inf[dst]) return {f - flow, ret}; // dstへ到達不可能
for (int i = 0; i < size_; ++i) h[i] += cost[i];
// src -> dst の最小コスト経路へ流せる量(df)を決定する。
Capacity df = flow;
for (int cur = dst; cur != src; cur = prev_node[cur]) {
df = std::min(df, g_[prev_node[cur]][prev_edge[cur]].cap);
}
flow -= df;
ret += df * h[dst];
// capの更新
for (int cur = dst; cur != src; cur = prev_node[cur]) {
edge &e = g_[prev_node[cur]][prev_edge[cur]];
e.cap -= df;
g_[cur][e.rev].cap += df;
}
}
return {f - flow, ret};
}
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 5 "Mylib/Graph/Matching/weighted_bipartite_matching.cpp"
namespace haar_lib {
template <typename T, typename MinCostFlow, bool MIN_MATCHING = false>
class weighted_bipartite_matching {
int L_, R_, s_, t_;
MinCostFlow f_;
public:
weighted_bipartite_matching() {}
weighted_bipartite_matching(int L, int R, bool arbitrary_flow = false) : 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, 0);
for (int i = 0; i < R_; ++i) f_.add_edge(L_ + i, t_, 1, 0);
if (arbitrary_flow) f_.add_edge(s_, t_, std::numeric_limits<int>::max(), 0);
}
void add_edge(int from, int to, T gain) {
assert(0 <= from and from < L_);
assert(0 <= to and to < R_);
f_.add_edge(from, L_ + to, 1, gain * (MIN_MATCHING ? 1 : -1));
}
T match(int flow) {
T ret = f_.min_cost_flow(s_, t_, flow).second;
return ret * (MIN_MATCHING ? 1 : -1);
}
auto get_matching() {
const auto g = f_.edges();
std::vector<std::tuple<int, int, T>> ret;
for (auto &e : g) {
if (not e.is_rev and e.from != s_ and e.to != t_ and e.cap == 0) {
ret.emplace_back(e.from, e.to - L_, e.cost * (MIN_MATCHING ? 1 : -1));
}
}
return ret;
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuple_vector.cpp"
#include <initializer_list>
#line 7 "Mylib/IO/input_tuple_vector.cpp"
namespace haar_lib {
template <typename T, size_t... I>
void input_tuple_vector_init(T &val, int N, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(std::get<I>(val).resize(N)), 0)...};
}
template <typename T, size_t... I>
void input_tuple_vector_helper(T &val, int i, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(std::cin >> std::get<I>(val)[i]), 0)...};
}
template <typename... Args>
auto input_tuple_vector(int N) {
std::tuple<std::vector<Args>...> ret;
input_tuple_vector_init(ret, N, std::make_index_sequence<sizeof...(Args)>());
for (int i = 0; i < N; ++i) {
input_tuple_vector_helper(ret, i, std::make_index_sequence<sizeof...(Args)>());
}
return ret;
}
} // namespace haar_lib
#line 8 "test/aoj/2293/main.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int n;
std::cin >> n;
auto [A, B] = hl::input_tuple_vector<int, int>(n);
std::vector<int> ls(A);
ls.insert(ls.end(), B.begin(), B.end());
std::sort(ls.begin(), ls.end());
ls.erase(std::unique(ls.begin(), ls.end()), ls.end());
hl::weighted_bipartite_matching<int, hl::minimum_cost_flow<int, int>> m(n, ls.size(), true);
for (int i = 0; i < n; ++i) {
m.add_edge(i, std::lower_bound(ls.begin(), ls.end(), A[i]) - ls.begin(), B[i]);
m.add_edge(i, std::lower_bound(ls.begin(), ls.end(), B[i]) - ls.begin(), A[i]);
}
int ans = m.match(n);
std::cout << ans << std::endl;
return 0;
}
test/aoj/2293/main.test.cpp
Minimum cost flow
(Mylib/Graph/Flow/minimum_cost_flow.cpp)