C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title グラフ/フロー/マッチング/二部グラフの重み付き最大マッチング * * verification-helper: IGNORE * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2429 */ #include <iostream> #include <string> #include <vector> #include "emthrm/graph/flow/matching/weighted_bipartite_matching.hpp" int main() { int n; std::cin >> n; std::vector<std::vector<int>> w(n, std::vector<int>(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { std:: cin >> w[i][j]; } } std::vector<std::vector<int>> e(n, std::vector<int>(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { std:: cin >> e[i][j]; } } std::vector<std::string> f(n); long long ans = 0; for (int i = 0; i < n; ++i) { std::cin >> f[i]; for (int j = 0; j < n; ++j) { if (f[i][j] == 'o') ans += e[i][j]; } } emthrm::WeightedBipartiteMatching<long long> weighted_bipartite_matching(n, n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { weighted_bipartite_matching.add_edge(i, j, f[i][j] == 'o' ? e[i][j] : -w[i][j]); } } std::cout << ans - weighted_bipartite_matching.solve() << '\n'; std::vector<std::string> taro(n, std::string(n, '.')); const std::vector<int> matching = weighted_bipartite_matching.matching(); for (int i = 0; i < n; ++i) { taro[i][matching[i]] = 'o'; } std::vector<int> r, c; std::vector<std::string> operate; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (f[i][j] != taro[i][j]) { r.emplace_back(i); c.emplace_back(j); operate.emplace_back(f[i][j] == 'o' ? "erase" : "write"); } } } const int cnt = r.size(); std::cout << cnt << '\n'; for (int i = 0; i < cnt; ++i) { std::cout << r[i] + 1 << ' ' << c[i] + 1 << ' ' << operate[i] << '\n'; } return 0; }
#line 1 "test/graph/flow/matching/weighted_bipartite_matching.test.cpp" /* * @title グラフ/フロー/マッチング/二部グラフの重み付き最大マッチング * * verification-helper: IGNORE * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2429 */ #include <iostream> #include <string> #include <vector> #line 1 "include/emthrm/graph/flow/matching/weighted_bipartite_matching.hpp" #include <cassert> #line 6 "include/emthrm/graph/flow/matching/weighted_bipartite_matching.hpp" #line 1 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp" #include <algorithm> #line 6 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp" #include <functional> #include <limits> #include <queue> #include <utility> #line 11 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp" namespace emthrm { template <typename T, typename U> struct MinimumCostSTFlow { struct Edge { int dst, rev; T cap; U cost; explicit Edge(const int dst, const T cap, const U cost, const int rev) : dst(dst), rev(rev), cap(cap), cost(cost) {} }; const U uinf; std::vector<std::vector<Edge>> graph; explicit MinimumCostSTFlow(const int n, const U uinf = std::numeric_limits<U>::max()) : uinf(uinf), graph(n), tinf(std::numeric_limits<T>::max()), n(n), has_negative_edge(false), prev_v(n, -1), prev_e(n, -1), dist(n), potential(n, 0) {} void add_edge(const int src, const int dst, const T cap, const U cost) { has_negative_edge |= cost < 0; graph[src].emplace_back(dst, cap, cost, graph[dst].size()); graph[dst].emplace_back(src, 0, -cost, graph[src].size() - 1); } U solve(const int s, const int t, T flow) { if (flow == 0) [[unlikely]] return 0; U res = 0; has_negative_edge ? bellman_ford(s) : dijkstra(s); while (true) { if (dist[t] == uinf) return uinf; res += calc(s, t, &flow); if (flow == 0) break; dijkstra(s); } return res; } U solve(const int s, const int t) { U res = 0; T flow = tinf; bellman_ford(s); while (potential[t] < 0 && dist[t] != uinf) { res += calc(s, t, &flow); dijkstra(s); } return res; } std::pair<T, U> minimum_cost_maximum_flow(const int s, const int t, const T flow) { if (flow == 0) [[unlikely]] return {0, 0}; T f = flow; U cost = 0; has_negative_edge ? bellman_ford(s) : dijkstra(s); while (dist[t] != uinf) { cost += calc(s, t, &f); if (f == 0) break; dijkstra(s); } return {flow - f, cost}; } private: const T tinf; const int n; bool has_negative_edge; std::vector<int> prev_v, prev_e; std::vector<U> dist, potential; std::priority_queue<std::pair<U, int>, std::vector<std::pair<U, int>>, std::greater<std::pair<U, int>>> que; void bellman_ford(const int s) { std::fill(dist.begin(), dist.end(), uinf); dist[s] = 0; bool is_updated = true; for (int step = 0; step < n && is_updated; ++step) { is_updated = false; for (int i = 0; i < n; ++i) { if (dist[i] == uinf) continue; for (int j = 0; std::cmp_less(j, graph[i].size()); ++j) { const Edge& e = graph[i][j]; if (e.cap > 0 && dist[e.dst] > dist[i] + e.cost) { dist[e.dst] = dist[i] + e.cost; prev_v[e.dst] = i; prev_e[e.dst] = j; is_updated = true; } } } } assert(!is_updated); for (int i = 0; i < n; ++i) { if (dist[i] != uinf) potential[i] += dist[i]; } } void dijkstra(const int s) { std::fill(dist.begin(), dist.end(), uinf); dist[s] = 0; que.emplace(0, s); while (!que.empty()) { const auto [d, ver] = que.top(); que.pop(); if (dist[ver] < d) continue; for (int i = 0; std::cmp_less(i, graph[ver].size()); ++i) { const Edge& e = graph[ver][i]; const U nxt = dist[ver] + e.cost + potential[ver] - potential[e.dst]; if (e.cap > 0 && dist[e.dst] > nxt) { dist[e.dst] = nxt; prev_v[e.dst] = ver; prev_e[e.dst] = i; que.emplace(dist[e.dst], e.dst); } } } for (int i = 0; i < n; ++i) { if (dist[i] != uinf) potential[i] += dist[i]; } } U calc(const int s, const int t, T* flow) { T f = *flow; for (int v = t; v != s; v = prev_v[v]) { f = std::min(f, graph[prev_v[v]][prev_e[v]].cap); } *flow -= f; for (int v = t; v != s; v = prev_v[v]) { Edge& e = graph[prev_v[v]][prev_e[v]]; e.cap -= f; graph[v][e.rev].cap += f; } return potential[t] * f; } }; } // namespace emthrm #line 8 "include/emthrm/graph/flow/matching/weighted_bipartite_matching.hpp" namespace emthrm { template <typename T> struct WeightedBipartiteMatching { explicit WeightedBipartiteMatching(const int left, const int right) : is_built(false), left(left), right(right), mcf(left + right + 2) {} void add_edge(const int src, const int dst, const T cost) { mcf.add_edge(src, left + dst, 1, -cost); } T solve() { assert(!is_built); is_built = true; const int s = left + right, t = left + right + 1; for (int i = 0; i < left; ++i) { mcf.add_edge(s, i, 1, 0); } for (int i = 0; i < right; ++i) { mcf.add_edge(left + i, t, 1, 0); } return -mcf.minimum_cost_maximum_flow(s, t, left).second; } std::vector<int> matching() const { assert(is_built); std::vector<int> res(left, -1); for (int i = 0; i < left; ++i) { for (const auto& e : mcf.graph[i]) { if (e.cap == 0 && left <= e.dst && e.dst < left + right) { res[i] = e.dst - left; break; } } } return res; } private: bool is_built; const int left, right; MinimumCostSTFlow<int, T> mcf; }; } // namespace emthrm #line 13 "test/graph/flow/matching/weighted_bipartite_matching.test.cpp" int main() { int n; std::cin >> n; std::vector<std::vector<int>> w(n, std::vector<int>(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { std:: cin >> w[i][j]; } } std::vector<std::vector<int>> e(n, std::vector<int>(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { std:: cin >> e[i][j]; } } std::vector<std::string> f(n); long long ans = 0; for (int i = 0; i < n; ++i) { std::cin >> f[i]; for (int j = 0; j < n; ++j) { if (f[i][j] == 'o') ans += e[i][j]; } } emthrm::WeightedBipartiteMatching<long long> weighted_bipartite_matching(n, n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { weighted_bipartite_matching.add_edge(i, j, f[i][j] == 'o' ? e[i][j] : -w[i][j]); } } std::cout << ans - weighted_bipartite_matching.solve() << '\n'; std::vector<std::string> taro(n, std::string(n, '.')); const std::vector<int> matching = weighted_bipartite_matching.matching(); for (int i = 0; i < n; ++i) { taro[i][matching[i]] = 'o'; } std::vector<int> r, c; std::vector<std::string> operate; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (f[i][j] != taro[i][j]) { r.emplace_back(i); c.emplace_back(j); operate.emplace_back(f[i][j] == 'o' ? "erase" : "write"); } } } const int cnt = r.size(); std::cout << cnt << '\n'; for (int i = 0; i < cnt; ++i) { std::cout << r[i] + 1 << ' ' << c[i] + 1 << ' ' << operate[i] << '\n'; } return 0; }