#line 1 "test/yosupo-judge/assignment/main.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/assignment"
#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 4 "Mylib/IO/input_vector.cpp"
namespace haar_lib {
template <typename T>
std::vector<T> input_vector(int N) {
std::vector<T> ret(N);
for (int i = 0; i < N; ++i) std::cin >> ret[i];
return ret;
}
template <typename T>
std::vector<std::vector<T>> input_vector(int N, int M) {
std::vector<std::vector<T>> ret(N);
for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
return ret;
}
} // namespace haar_lib
#line 3 "Mylib/IO/join.cpp"
#include <sstream>
#include <string>
namespace haar_lib {
template <typename Iter>
std::string join(Iter first, Iter last, std::string delim = " ") {
std::stringstream s;
for (auto it = first; it != last; ++it) {
if (it != first) s << delim;
s << *it;
}
return s.str();
}
} // namespace haar_lib
#line 9 "test/yosupo-judge/assignment/main.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N;
std::cin >> N;
hl::weighted_bipartite_matching<int64_t, hl::minimum_cost_flow<int, int64_t>, true> m(N, N);
auto a = hl::input_vector<int64_t>(N, N);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
m.add_edge(i, j, a[i][j]);
}
}
auto ans = m.match(N);
std::cout << ans << std::endl;
auto matching = m.get_matching();
std::vector<int> p(N);
for (auto [i, j, c] : matching) {
p[i] = j;
}
std::cout << hl::join(p.begin(), p.end()) << "\n";
return 0;
}
test/yosupo-judge/assignment/main.test.cpp
Minimum cost flow
(Mylib/Graph/Flow/minimum_cost_flow.cpp)