proconlib
This documentation is automatically generated by competitive-verifier/competitive-verifier
tests/weighted_bipartite_matching/maximize.test.cpp
- View this file on GitHub
- Last update: 2025-01-26 15:10:23+09:00
- Problem: https://atcoder.jp/contests/acl1/tasks/acl1_c
Depends on
std::abs(x) extended for my library (tools/abs.hpp)- chmin function (tools/chmin.hpp)
- std::greater by second (tools/greater_by_second.hpp)
- Combine hash values (tools/hash_combine.hpp)
- Solver of minimum-cost flow problem (tools/mcf_graph.hpp)
- The number of nanoseconds that have elapsed since epoch (tools/now.hpp)
- Hash of std::tuple (tools/tuple_hash.hpp)
- Vector (tools/vector.hpp)
- Two dimensional vector (tools/vector2.hpp)
- Matching on weighted bipartite graph (tools/weighted_bipartite_matching.hpp)
Code
// competitive-verifier: PROBLEM https://atcoder.jp/contests/acl1/tasks/acl1_c
// competitive-verifier: IGNORE
#include <iostream>
#include <vector>
#include <string>
#include <variant>
#include <queue>
#include "tools/weighted_bipartite_matching.hpp"
#include "tools/vector2.hpp"
using ll = long long;
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
ll N, M;
std::cin >> N >> M;
std::vector<std::string> S(N);
for (auto& S_i : S) std::cin >> S_i;
tools::weighted_bipartite_matching<ll> graph(N * M, N * M, true);
ll number_of_pieces = 0;
for (ll y1 = 0; y1 < N; ++y1) {
for (ll x1 = 0; x1 < M; ++x1) {
if (S[y1][x1] == 'o') {
++number_of_pieces;
std::queue<tools::vector2<ll>> queue;
queue.emplace(x1, y1);
auto will_visit = std::vector(N, std::vector(M, false));
will_visit[y1][x1] = true;
while (!queue.empty()) {
const auto here = queue.front();
queue.pop();
graph.add_edge(y1 * M + x1, here.y * M + here.x, (here.y - y1) + (here.x - x1));
if (here.y + 1 < N && !will_visit[here.y + 1][here.x] && S[here.y + 1][here.x] != '#') {
queue.emplace(here.x, here.y + 1);
will_visit[here.y + 1][here.x] = true;
}
if (here.x + 1 < M && !will_visit[here.y][here.x + 1] && S[here.y][here.x + 1] != '#') {
queue.emplace(here.x + 1, here.y);
will_visit[here.y][here.x + 1] = true;
}
}
}
}
}
std::cout << graph.query(number_of_pieces)->first << '\n';
return 0;
}
#line 1 "tests/weighted_bipartite_matching/maximize.test.cpp"
// competitive-verifier: PROBLEM https://atcoder.jp/contests/acl1/tasks/acl1_c
// competitive-verifier: IGNORE
#include <iostream>
#include <vector>
#include <string>
#include <variant>
#include <queue>
#line 1 "tools/weighted_bipartite_matching.hpp"
#include <cstddef>
#line 6 "tools/weighted_bipartite_matching.hpp"
#include <cassert>
#include <optional>
#include <utility>
#include <limits>
#line 1 "tools/mcf_graph.hpp"
#line 9 "tools/mcf_graph.hpp"
#include <numeric>
#include <stack>
#include <iterator>
#include <algorithm>
#line 14 "tools/mcf_graph.hpp"
#include <tuple>
#line 1 "tools/chmin.hpp"
#include <type_traits>
#line 6 "tools/chmin.hpp"
namespace tools {
template <typename M, typename N>
bool chmin(M& lhs, const N& rhs) {
bool updated;
if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
updated = ::std::cmp_less(rhs, lhs);
} else {
updated = rhs < lhs;
}
if (updated) lhs = rhs;
return updated;
}
}
#line 1 "tools/greater_by_second.hpp"
#line 5 "tools/greater_by_second.hpp"
namespace tools {
class greater_by_second {
public:
template <class T1, class T2>
bool operator()(const ::std::pair<T1, T2>& x, const ::std::pair<T1, T2>& y) const {
return x.second > y.second;
}
};
}
#line 17 "tools/mcf_graph.hpp"
namespace tools {
template <typename Cap, typename Cost>
class mcf_graph {
public:
struct edge {
int from, to;
Cap cap, flow;
Cost cost;
};
private:
::std::vector<::std::vector<int>> m_graph;
::std::vector<::tools::mcf_graph<Cap, Cost>::edge> m_edges;
::std::vector<::std::pair<Cap, Cost>> m_slope;
::std::vector<Cost> m_potentials;
bool m_filled_negative_cycles;
::std::optional<bool> m_is_dag;
bool m_calculated_potentials;
int size() const {
return this->m_graph.size();
}
public:
mcf_graph() = default;
mcf_graph(const ::tools::mcf_graph<Cap, Cost>&) = default;
mcf_graph(::tools::mcf_graph<Cap, Cost>&&) = default;
~mcf_graph() = default;
::tools::mcf_graph<Cap, Cost>& operator=(const ::tools::mcf_graph<Cap, Cost>&) = default;
::tools::mcf_graph<Cap, Cost>& operator=(::tools::mcf_graph<Cap, Cost>&&) = default;
explicit mcf_graph(const int n) : m_graph(n), m_slope({::std::pair<Cap, Cost>(0, 0)}), m_potentials(n, 0), m_filled_negative_cycles(false), m_calculated_potentials(false) {
}
int add_edge(const int from, const int to, const Cap cap, const Cost cost) {
assert(0 <= from && from < this->size());
assert(0 <= to && to < this->size());
assert(0 <= cap);
assert(cost != ::std::numeric_limits<Cost>::min());
assert(cost != ::std::numeric_limits<Cost>::max());
this->m_graph[from].push_back(this->m_edges.size());
this->m_edges.push_back(::tools::mcf_graph<Cap, Cost>::edge({from, to, cap, 0, cost}));
this->m_graph[to].push_back(this->m_edges.size());
this->m_edges.push_back(::tools::mcf_graph<Cap, Cost>::edge({to, from, cap, cap, -cost}));
return this->m_edges.size() / 2 - 1;
}
private:
void fill_negative_cycles() {
::std::vector<::std::pair<::std::vector<int>, ::std::vector<int>>> scc({::std::make_pair(::std::vector<int>(this->size()), ::std::vector<int>(this->m_edges.size()))});
::std::iota(scc[0].first.begin(), scc[0].first.end(), 0);
::std::iota(scc[0].second.begin(), scc[0].second.end(), 0);
::std::vector<int> scc_inv(this->size(), 0);
::std::stack<int> scc_stack({0});
::std::vector<bool> will_visit(this->size());
::std::vector<Cost> dist(this->size());
::std::vector<int> prev(this->size());
// Loop until every strongly connected component contains no negative cycles.
while (!scc_stack.empty()) {
const auto scc_id = scc_stack.top();
scc_stack.pop();
::std::vector<int> scc_vertices;
::std::vector<int> scc_edge_ids;
scc_vertices.swap(scc[scc_id].first);
scc_edge_ids.swap(scc[scc_id].second);
// scc[scc_id] might be decomposed into smaller strongly connected components, so check and decompose it.
::std::stack<int> ordered_by_dfs;
for (const auto v : scc_vertices) {
will_visit[v] = false;
}
for (const auto root : scc_vertices) {
if (will_visit[root]) continue;
::std::stack<::std::pair<bool, int>> stack;
stack.emplace(true, root);
while (!stack.empty()) {
const auto [pre, here] = stack.top();
stack.pop();
if (pre) {
if (will_visit[here]) continue;
will_visit[here] = true;
stack.emplace(false, here);
for (const auto edge_id : this->m_graph[here]) {
const auto& edge = this->m_edges[edge_id];
if (edge.flow < edge.cap && !will_visit[edge.to]) {
stack.emplace(true, edge.to);
}
}
} else {
ordered_by_dfs.push(here);
}
}
}
::std::vector<int> new_scc_ids;
for (const auto v : scc_vertices) {
will_visit[v] = false;
}
while (!ordered_by_dfs.empty()) {
const auto root = ordered_by_dfs.top();
ordered_by_dfs.pop();
if (will_visit[root]) continue;
if (new_scc_ids.empty()) {
new_scc_ids.push_back(scc_id);
} else {
new_scc_ids.push_back(scc.size());
scc.emplace_back();
}
::std::stack<int> stack({root});
will_visit[root] = true;
while (!stack.empty()) {
const auto here = stack.top();
stack.pop();
scc[new_scc_ids.back()].first.emplace_back();
scc_inv[here] = new_scc_ids.back();
for (const auto edge_id : this->m_graph[here]) {
const auto& edge = this->m_edges[edge_id];
const auto& rev = this->m_edges[edge_id ^ 1];
if (rev.flow < rev.cap && !will_visit[edge.to]) {
stack.push(edge.to);
will_visit[edge.to] = true;
}
}
}
}
for (const auto edge_id : scc_edge_ids) {
const auto& edge = this->m_edges[edge_id];
if (scc_inv[edge.from] == scc_inv[edge.to]) {
scc[scc_inv[edge.from]].second.push_back(edge_id);
}
}
// Now, scc[new_scc_id] is truly a strongly connected component.
// Check whether it contains any negative cycles using Bellman-Ford algorithm.
for (const auto new_scc_id : new_scc_ids) {
const auto& [new_scc_vertices, new_scc_edge_ids] = scc[new_scc_id];
for (const auto v : new_scc_vertices) {
dist[v] = ::std::numeric_limits<Cost>::max();
prev[v] = -1;
}
dist[new_scc_vertices[0]] = 0;
for (int i = 0; i < ::std::ssize(new_scc_vertices) - 1; ++i) {
for (const auto edge_id : new_scc_edge_ids) {
const auto& edge = this->m_edges[edge_id];
if (edge.flow < edge.cap && dist[edge.from] < ::std::numeric_limits<Cost>::max() && ::tools::chmin(dist[edge.to], dist[edge.from] + edge.cost)) {
prev[edge.to] = edge_id;
}
}
}
for (const auto edge_id : new_scc_edge_ids) {
auto& edge = this->m_edges[edge_id];
auto& rev = this->m_edges[edge_id ^ 1];
if (edge.flow < edge.cap && dist[edge.from] < ::std::numeric_limits<Cost>::max() && ::tools::chmin(dist[edge.to], dist[edge.from] + edge.cost)) {
// We found a negative cycle, so fill it.
// Later, we will check whether the component can be decomposed into smaller ones.
Cap cap = edge.cap - edge.flow;
for (int v = edge.from; v != edge.to; v = this->m_edges[prev[v]].from) {
const auto& current_edge = this->m_edges[prev[v]];
::tools::chmin(cap, current_edge.cap - current_edge.flow);
}
edge.flow += cap;
rev.flow -= cap;
this->m_slope.back().second += cap * edge.cost;
for (int v = edge.from; v != edge.to; v = this->m_edges[prev[v]].from) {
auto& current_edge = this->m_edges[prev[v]];
auto& current_rev = this->m_edges[prev[v] ^ 1];
current_edge.flow += cap;
current_rev.flow -= cap;
this->m_slope.back().second += cap * current_edge.cost;
}
scc_stack.push(new_scc_id);
break;
}
}
}
}
this->m_is_dag = ::std::all_of(scc.begin(), scc.end(), [](const auto& pair) { return pair.first.size() == 1; });
}
// This is for the first try to find the shortest path in a DAG with some negative edges.
// We use topological sorting + DP. (O(V + E) time)
::std::pair<::std::vector<Cost>, ::std::vector<int>> find_shortest_path_by_dp(const int s) {
::std::vector<Cost> dist(this->size(), ::std::numeric_limits<Cost>::max());
::std::vector<int> prev(this->size(), -1);
::std::vector<int> indeg(this->size(), 0);
for (const auto& edge : this->m_edges) {
if (edge.flow < edge.cap) {
++indeg[edge.to];
}
}
::std::queue<int> queue;
for (int v = 0; v < this->size(); ++v) {
if (indeg[v] == 0) {
queue.push(v);
}
}
dist[s] = 0;
while (!queue.empty()) {
const auto here = queue.front();
queue.pop();
for (const auto edge_id : this->m_graph[here]) {
const auto& edge = this->m_edges[edge_id];
if (edge.flow < edge.cap) {
if (dist[edge.from] < ::std::numeric_limits<Cost>::max() && ::tools::chmin(dist[edge.to], dist[edge.from] + edge.cost)) {
prev[edge.to] = edge_id;
}
--indeg[edge.to];
if (indeg[edge.to] == 0) {
queue.push(edge.to);
}
}
}
}
return ::std::make_pair(dist, prev);
}
// This is for the first try to find the shortest path in a graph with some negative edges and some non-negative cycles.
// We use Bellman-Ford algorithm. (O(VE) time)
::std::pair<::std::vector<Cost>, ::std::vector<int>> find_shortest_path_by_bellman_ford(const int s) {
::std::vector<Cost> dist(this->size(), ::std::numeric_limits<Cost>::max());
::std::vector<int> prev(this->size(), -1);
dist[s] = 0;
for (int i = 0; i < this->size() - 1; ++i) {
for (int edge_id = 0; edge_id < ::std::ssize(this->m_edges); ++edge_id) {
const auto& edge = this->m_edges[edge_id];
if (edge.flow < edge.cap && dist[edge.from] < ::std::numeric_limits<Cost>::max() && ::tools::chmin(dist[edge.to], dist[edge.from] + edge.cost)) {
prev[edge.to] = edge_id;
}
}
}
#ifndef NDEBUG
for (const auto& edge : this->m_edges) {
if (edge.flow < edge.cap && dist[edge.from] < ::std::numeric_limits<Cost>::max()) {
assert(dist[edge.to] <= dist[edge.from] + edge.cost);
}
}
#endif
return ::std::make_pair(dist, prev);
}
// This is for finding the shortest path in a graph without negative edges.
// We use Dijkstra's algorithm with potentials. (O((V + E) logV) time)
::std::pair<::std::vector<Cost>, ::std::vector<int>> find_shortest_path_by_dijkstra(const int s) {
::std::vector<Cost> dist(this->size(), ::std::numeric_limits<Cost>::max());
::std::vector<int> prev(this->size(), -1);
#ifndef NDEBUG
for (const auto& edge : this->m_edges) {
if (edge.flow < edge.cap && this->m_potentials[edge.from] < ::std::numeric_limits<Cost>::max() && this->m_potentials[edge.to] < ::std::numeric_limits<Cost>::max()) {
assert(edge.cost + (this->m_potentials[edge.from] - this->m_potentials[edge.to]) >= 0);
}
}
#endif
dist[s] = 0;
::std::priority_queue<::std::pair<int, Cost>, ::std::vector<::std::pair<int, Cost>>, ::tools::greater_by_second> tasks;
tasks.emplace(s, 0);
while (!tasks.empty()) {
const auto [here, d] = tasks.top();
tasks.pop();
if (dist[here] < d) continue;
for (const auto edge_id : this->m_graph[here]) {
const auto& edge = this->m_edges[edge_id];
if (edge.flow < edge.cap && dist[edge.from] < ::std::numeric_limits<Cost>::max()) {
assert(this->m_potentials[edge.from] < ::std::numeric_limits<Cost>::max());
assert(this->m_potentials[edge.to] < ::std::numeric_limits<Cost>::max());
if (::tools::chmin(dist[edge.to], dist[edge.from] + edge.cost + (this->m_potentials[edge.from] - this->m_potentials[edge.to]))) {
prev[edge.to] = edge_id;
tasks.emplace(edge.to, dist[edge.to]);
}
}
}
}
return ::std::make_pair(dist, prev);
}
public:
::std::vector<::std::pair<Cap, Cost>> slope(const int s, const int t, const Cap flow_limit) {
assert(0 <= s && s < this->size());
assert(0 <= t && t < this->size());
assert(s != t);
assert(this->m_slope.back().first <= flow_limit);
if (!this->m_filled_negative_cycles) {
this->fill_negative_cycles();
this->m_filled_negative_cycles = true;
}
while (this->m_slope.back().first < flow_limit) {
::std::vector<Cost> dist;
::std::vector<int> prev;
if (!this->m_calculated_potentials) {
const bool has_negative_edge = ::std::any_of(this->m_edges.begin(), this->m_edges.end(), [](const auto& edge) { return edge.flow < edge.cap && edge.cost < 0; });
if (has_negative_edge) {
if (*this->m_is_dag) {
::std::tie(dist, prev) = this->find_shortest_path_by_dp(s);
} else {
::std::tie(dist, prev) = this->find_shortest_path_by_bellman_ford(s);
}
} else {
::std::tie(dist, prev) = this->find_shortest_path_by_dijkstra(s);
}
} else {
::std::tie(dist, prev) = this->find_shortest_path_by_dijkstra(s);
}
if (dist[t] == ::std::numeric_limits<Cost>::max()) break;
for (int i = 0; i < this->size(); ++i) {
if (dist[i] < ::std::numeric_limits<Cost>::max()) {
this->m_potentials[i] += dist[i];
} else {
this->m_potentials[i] = ::std::numeric_limits<Cost>::max();
}
}
this->m_calculated_potentials = true;
this->m_is_dag = ::std::nullopt;
// Fill the shortest path.
Cap cap = flow_limit - this->m_slope.back().first;
for (int v = t; v != s; v = this->m_edges[prev[v]].from) {
const auto& edge = this->m_edges[prev[v]];
::tools::chmin(cap, edge.cap - edge.flow);
}
Cost cost = 0;
for (int v = t; v != s; v = this->m_edges[prev[v]].from) {
auto& edge = this->m_edges[prev[v]];
auto& rev = this->m_edges[prev[v] ^ 1];
edge.flow += cap;
rev.flow -= cap;
cost += cap * edge.cost;
}
if ([&]() {
if (this->m_slope.size() < 2) return true;
auto dx1 = this->m_slope.back().first - this->m_slope.rbegin()[1].first;
auto dy1 = this->m_slope.back().second - this->m_slope.rbegin()[1].second;
const auto gcd1 = ::std::gcd(dx1, dy1);
dx1 /= gcd1;
dy1 /= gcd1;
auto dx2 = cap;
auto dy2 = cost;
const auto gcd2 = ::std::gcd(dx2, dy2);
dx2 /= gcd2;
dy2 /= gcd2;
return !(dx1 == dx2 && dy1 == dy2);
}()) {
this->m_slope.emplace_back(this->m_slope.back().first + cap, this->m_slope.back().second + cost);
} else {
this->m_slope.back().first += cap;
this->m_slope.back().second += cost;
}
}
return this->m_slope;
}
::std::vector<::std::pair<Cap, Cost>> slope(const int s, const int t) {
return this->slope(s, t, ::std::numeric_limits<Cap>::max());
}
::std::pair<Cap, Cost> flow(const int s, const int t, const Cap flow_limit) {
return this->slope(s, t, flow_limit).back();
}
::std::pair<Cap, Cost> flow(const int s, const int t) {
return this->slope(s, t).back();
}
::tools::mcf_graph<Cap, Cost>::edge get_edge(const int i) const {
assert(0 <= i && i < ::std::ssize(this->m_edges) / 2);
return this->m_edges[i * 2];
}
::std::vector<::tools::mcf_graph<Cap, Cost>::edge> edges() const {
::std::vector<::tools::mcf_graph<Cap, Cost>::edge> result;
for (int edge_id = 0; edge_id < ::std::ssize(this->m_edges); edge_id += 2) {
result.push_back(this->m_edges[edge_id]);
}
return result;
}
};
}
#line 12 "tools/weighted_bipartite_matching.hpp"
namespace tools {
template <typename W>
class weighted_bipartite_matching {
public:
struct edge {
::std::size_t id;
::std::size_t from;
::std::size_t to;
W weight;
};
private:
::std::size_t m_size1;
::std::size_t m_size2;
bool m_maximize;
::tools::mcf_graph<int, W> m_graph;
::std::vector<edge> m_edges;
public:
weighted_bipartite_matching() = default;
weighted_bipartite_matching(const ::tools::weighted_bipartite_matching<W>&) = default;
weighted_bipartite_matching(::tools::weighted_bipartite_matching<W>&&) = default;
~weighted_bipartite_matching() = default;
::tools::weighted_bipartite_matching<W>& operator=(const ::tools::weighted_bipartite_matching<W>&) = default;
::tools::weighted_bipartite_matching<W>& operator=(::tools::weighted_bipartite_matching<W>&&) = default;
weighted_bipartite_matching(const ::std::size_t size1, const ::std::size_t size2, const bool maximize) :
m_size1(size1), m_size2(size2), m_maximize(maximize), m_graph(size1 + size2 + 2) {
for (::std::size_t i = 0; i < size1; ++i) {
this->m_graph.add_edge(size1 + size2, i, 1, 0);
}
for (::std::size_t i = 0; i < size2; ++i) {
this->m_graph.add_edge(size1 + i, size1 + size2 + 1, 1, 0);
}
}
::std::size_t size1() const {
return this->m_size1;
}
::std::size_t size2() const {
return this->m_size2;
}
::std::size_t add_edge(const ::std::size_t i, const ::std::size_t j, const W& w) {
assert(i < this->size1());
assert(j < this->size2());
this->m_graph.add_edge(i, this->m_size1 + j, 1, this->m_maximize ? -w : w);
this->m_edges.emplace_back(edge({this->m_edges.size(), i, j, w}));
return this->m_edges.size() - 1;
}
const edge& get_edge(const ::std::size_t k) const {
assert(k < this->m_edges.size());
return this->m_edges[k];
}
const ::std::vector<edge>& edges() const {
return this->m_edges;
}
::std::optional<::std::pair<W, ::std::vector<::std::size_t>>> query(const ::std::size_t k) {
const auto [flow, cost] = this->m_graph.flow(this->m_size1 + this->m_size2, this->m_size1 + this->m_size2 + 1, k);
if (flow < static_cast<int>(k)) return ::std::nullopt;
::std::vector<::std::size_t> edges;
for (::std::size_t i = 0; i < this->m_edges.size(); ++i) {
if (this->m_graph.get_edge(this->m_size1 + this->m_size2 + i).flow == 1) {
edges.push_back(i);
}
}
return ::std::make_optional(::std::make_pair(this->m_maximize ? -cost : cost, edges));
}
::std::pair<W, ::std::vector<::std::size_t>> query() {
auto tmp_graph = this->m_graph;
int min_cost_flow = 0;
auto min_cost = ::std::numeric_limits<W>::max();
for (const auto& [flow, cost] : tmp_graph.slope(this->m_size1 + this->m_size2, this->m_size1 + this->m_size2 + 1)) {
if (::tools::chmin(min_cost, cost)) {
min_cost_flow = flow;
}
}
const auto [flow, cost] = this->m_graph.flow(this->m_size1 + this->m_size2, this->m_size1 + this->m_size2 + 1, min_cost_flow);
::std::vector<::std::size_t> edges;
for (::std::size_t i = 0; i < this->m_edges.size(); ++i) {
if (this->m_graph.get_edge(this->m_size1 + this->m_size2 + i).flow == 1) {
edges.push_back(i);
}
}
return ::std::make_pair(this->m_maximize ? -cost : cost, edges);
}
};
}
#line 1 "tools/vector2.hpp"
#line 1 "tools/vector.hpp"
#line 5 "tools/vector.hpp"
#include <array>
#include <initializer_list>
#line 14 "tools/vector.hpp"
#include <cmath>
#line 17 "tools/vector.hpp"
#include <functional>
#line 1 "tools/abs.hpp"
namespace tools {
constexpr float abs(const float x) {
return x < 0 ? -x : x;
}
constexpr double abs(const double x) {
return x < 0 ? -x : x;
}
constexpr long double abs(const long double x) {
return x < 0 ? -x : x;
}
constexpr int abs(const int x) {
return x < 0 ? -x : x;
}
constexpr long abs(const long x) {
return x < 0 ? -x : x;
}
constexpr long long abs(const long long x) {
return x < 0 ? -x : x;
}
constexpr unsigned int abs(const unsigned int x) {
return x;
}
constexpr unsigned long abs(const unsigned long x) {
return x;
}
constexpr unsigned long long abs(const unsigned long long x) {
return x;
}
}
#line 1 "tools/tuple_hash.hpp"
#line 1 "tools/now.hpp"
#include <chrono>
namespace tools {
inline long long now() {
return ::std::chrono::duration_cast<::std::chrono::nanoseconds>(::std::chrono::high_resolution_clock::now().time_since_epoch()).count();
}
}
#line 1 "tools/hash_combine.hpp"
#line 6 "tools/hash_combine.hpp"
// Source: https://github.com/google/cityhash/blob/f5dc54147fcce12cefd16548c8e760d68ac04226/src/city.h
// License: MIT
// Author: Google Inc.
// Copyright (c) 2011 Google, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
namespace tools {
template <typename T>
void hash_combine(::std::size_t& seed, const T& v) {
static const ::std::hash<T> hasher;
static constexpr ::std::size_t k_mul = 0x9ddfea08eb382d69ULL;
::std::size_t a = (hasher(v) ^ seed) * k_mul;
a ^= (a >> 47);
::std::size_t b = (seed ^ a) * k_mul;
b ^= (b >> 47);
seed = b * k_mul;
}
}
#line 11 "tools/tuple_hash.hpp"
namespace tools {
template <typename... Ts>
struct tuple_hash {
template <::std::size_t I = sizeof...(Ts) - 1>
::std::size_t operator()(const ::std::tuple<Ts...>& key) const {
if constexpr (I == ::std::numeric_limits<::std::size_t>::max()) {
static const ::std::size_t seed = ::tools::now();
return seed;
} else {
::std::size_t seed = this->operator()<I - 1>(key);
::tools::hash_combine(seed, ::std::get<I>(key));
return seed;
}
}
};
}
#line 21 "tools/vector.hpp"
namespace tools {
namespace detail {
namespace vector {
template <typename T, ::std::size_t N>
class members {
protected:
constexpr static bool variable_sized = false;
constexpr static bool has_aliases = false;
::std::array<T, N> m_values;
members() : m_values() {}
members(const ::std::initializer_list<T> il) : m_values(il) {
assert(il.size() == N);
}
};
template <typename T>
class members<T, 2> {
protected:
constexpr static bool variable_sized = false;
constexpr static bool has_aliases = true;
::std::array<T*, 2> m_values;
members() : m_values{&this->x, &this->y} {}
members(const T& x, const T& y) : m_values{&this->x, &this->y}, x(x), y(y) {}
members(const ::std::initializer_list<T> il) : m_values{&this->x, &this->y}, x(il.begin()[0]), y(il.begin()[1]) {
assert(il.size() == 2);
}
public:
T x;
T y;
};
template <typename T>
class members<T, 3> {
protected:
constexpr static bool variable_sized = false;
constexpr static bool has_aliases = true;
::std::array<T*, 3> m_values;
members() : m_values{&this->x, &this->y, &this->z} {}
members(const T& x, const T& y, const T& z) : m_values{&this->x, &this->y, &this->z}, x(x), y(y), z(z) {}
members(const ::std::initializer_list<T> il) : m_values{&this->x, &this->y, &this->z}, x(il.begin()[0]), y(il.begin()[1]), z(il.begin()[2]) {
assert(il.size() == 3);
}
public:
T x;
T y;
T z;
};
template <typename T>
class members<T, 4> {
protected:
constexpr static bool variable_sized = false;
constexpr static bool has_aliases = true;
::std::array<T*, 4> m_values;
members() : m_values{&this->x, &this->y, &this->z, &this->w} {}
members(const T& x, const T& y, const T& z, const T& w) : m_values{&this->x, &this->y, &this->z, &this->w}, x(x), y(y), z(z), w(w) {}
members(const ::std::initializer_list<T> il) : m_values{&this->x, &this->y, &this->z, &this->w}, x(il.begin()[0]), y(il.begin()[1]), z(il.begin()[2]), w(il.begin()[3]) {
assert(il.size() == 4);
}
public:
T x;
T y;
T z;
T w;
};
template <typename T>
class members<T, ::std::numeric_limits<::std::size_t>::max()> {
protected:
constexpr static bool variable_sized = true;
constexpr static bool has_aliases = false;
::std::vector<T> m_values;
members() = default;
members(const ::std::size_t n) : m_values(n) {}
members(const ::std::size_t n, const T& value) : m_values(n, value) {}
template <typename InputIter>
members(const InputIter first, const InputIter last) : m_values(first, last) {}
members(const ::std::initializer_list<T> il) : m_values(il) {}
};
}
}
template <typename T, ::std::size_t N = ::std::numeric_limits<::std::size_t>::max()>
class vector : public ::tools::detail::vector::members<T, N> {
private:
using Base = ::tools::detail::vector::members<T, N>;
using F = ::std::conditional_t<::std::is_floating_point_v<T>, T, double>;
using V = ::tools::vector<T, N>;
constexpr static bool variable_sized = Base::variable_sized;
constexpr static bool has_aliases = Base::has_aliases;
public:
using reference = T&;
using const_reference = const T&;
using size_type = ::std::size_t;
using difference_type = ::std::ptrdiff_t;
using pointer = T*;
using const_pointer = const T*;
using value_type = T;
class iterator {
private:
V* m_parent;
size_type m_i;
public:
using difference_type = ::std::ptrdiff_t;
using value_type = T;
using reference = T&;
using pointer = T*;
using iterator_category = ::std::random_access_iterator_tag;
iterator() = default;
iterator(const iterator&) = default;
iterator(iterator&&) = default;
~iterator() = default;
iterator& operator=(const iterator&) = default;
iterator& operator=(iterator&&) = default;
iterator(V * const parent, const size_type i) : m_parent(parent), m_i(i) {}
reference operator*() const {
return (*this->m_parent)[this->m_i];
}
pointer operator->() const {
return &(*(*this));
}
iterator& operator++() {
++this->m_i;
return *this;
}
iterator operator++(int) {
const auto self = *this;
++*this;
return self;
}
iterator& operator--() {
--this->m_i;
return *this;
}
iterator operator--(int) {
const auto self = *this;
--*this;
return self;
}
iterator& operator+=(const difference_type n) {
this->m_i += n;
return *this;
}
iterator& operator-=(const difference_type n) {
this->m_i -= n;
return *this;
}
friend iterator operator+(const iterator& self, const difference_type n) {
return iterator(self) += n;
}
friend iterator operator+(const difference_type n, const iterator& self) {
return iterator(self) += n;
}
friend iterator operator-(const iterator& self, const difference_type n) {
return iterator(self) -= n;
}
friend difference_type operator-(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return static_cast<difference_type>(lhs.m_i) - static_cast<difference_type>(rhs.m_i);
}
reference operator[](const difference_type n) const {
return *(*this + n);
}
friend bool operator==(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i == rhs.m_i;
}
friend bool operator!=(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i != rhs.m_i;
}
friend bool operator<(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i < rhs.m_i;
}
friend bool operator<=(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i <= rhs.m_i;
}
friend bool operator>(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i > rhs.m_i;
}
friend bool operator>=(const iterator& lhs, const iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i >= rhs.m_i;
}
};
class const_iterator {
private:
const V *m_parent;
size_type m_i;
public:
using difference_type = ::std::ptrdiff_t;
using value_type = T;
using reference = const T&;
using pointer = const T*;
using iterator_category = ::std::random_access_iterator_tag;
const_iterator() = default;
const_iterator(const const_iterator&) = default;
const_iterator(const_iterator&&) = default;
~const_iterator() = default;
const_iterator& operator=(const const_iterator&) = default;
const_iterator& operator=(const_iterator&&) = default;
const_iterator(const V * const parent, const size_type i) : m_parent(parent), m_i(i) {}
reference operator*() const {
return (*this->m_parent)[this->m_i];
}
pointer operator->() const {
return &(*(*this));
}
const_iterator& operator++() {
++this->m_i;
return *this;
}
const_iterator operator++(int) {
const auto self = *this;
++*this;
return self;
}
const_iterator& operator--() {
--this->m_i;
return *this;
}
const_iterator operator--(int) {
const auto self = *this;
--*this;
return self;
}
const_iterator& operator+=(const difference_type n) {
this->m_i += n;
return *this;
}
const_iterator& operator-=(const difference_type n) {
this->m_i -= n;
return *this;
}
friend const_iterator operator+(const const_iterator& self, const difference_type n) {
return const_iterator(self) += n;
}
friend const_iterator operator+(const difference_type n, const const_iterator& self) {
return const_iterator(self) += n;
}
friend const_iterator operator-(const const_iterator& self, const difference_type n) {
return const_iterator(self) -= n;
}
friend difference_type operator-(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return static_cast<difference_type>(lhs.m_i) - static_cast<difference_type>(rhs.m_i);
}
reference operator[](const difference_type n) const {
return *(*this + n);
}
friend bool operator==(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i == rhs.m_i;
}
friend bool operator!=(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i != rhs.m_i;
}
friend bool operator<(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i < rhs.m_i;
}
friend bool operator<=(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i <= rhs.m_i;
}
friend bool operator>(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i > rhs.m_i;
}
friend bool operator>=(const const_iterator& lhs, const const_iterator& rhs) {
assert(lhs.m_parent == rhs.m_parent);
return lhs.m_i >= rhs.m_i;
}
};
using reverse_iterator = ::std::reverse_iterator<iterator>;
using const_reverse_iterator = ::std::reverse_iterator<const_iterator>;
vector() = default;
vector(const V& other) : Base() {
if constexpr (has_aliases) {
::std::copy(other.begin(), other.end(), this->begin());
} else {
this->m_values = other.m_values;
}
}
vector(V&& other) noexcept {
if constexpr (has_aliases) {
::std::copy(other.begin(), other.end(), this->begin());
} else {
this->m_values = ::std::move(other.m_values);
}
}
~vector() = default;
V& operator=(const V& other) {
if constexpr (has_aliases) {
::std::copy(other.begin(), other.end(), this->begin());
} else {
this->m_values = other.m_values;
}
return *this;
}
V& operator=(V&& other) noexcept {
if constexpr (has_aliases) {
::std::copy(other.begin(), other.end(), this->begin());
} else {
this->m_values = ::std::move(other.m_values);
}
return *this;
}
template <bool SFINAE = variable_sized, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
explicit vector(size_type n) : Base(n) {}
template <bool SFINAE = variable_sized, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
vector(size_type n, const_reference value) : Base(n, value) {}
template <typename InputIter, bool SFINAE = variable_sized, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
vector(const InputIter first, const InputIter last) : Base(first, last) {}
template <bool SFINAE = N == 2, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
vector(const T& x, const T& y) : Base(x, y) {}
template <bool SFINAE = N == 3, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
vector(const T& x, const T& y, const T& z) : Base(x, y, z) {}
template <bool SFINAE = N == 4, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
vector(const T& x, const T& y, const T& z, const T& w) : Base(x, y, z, w) {}
vector(const ::std::initializer_list<T> il) : Base(il) {}
iterator begin() noexcept { return iterator(this, 0); }
const_iterator begin() const noexcept { return const_iterator(this, 0); }
const_iterator cbegin() const noexcept { return const_iterator(this, 0); }
iterator end() noexcept { return iterator(this, this->size()); }
const_iterator end() const noexcept { return const_iterator(this, this->size()); }
const_iterator cend() const noexcept { return const_iterator(this, this->size()); }
reverse_iterator rbegin() noexcept { return ::std::make_reverse_iterator(this->end()); }
const_reverse_iterator rbegin() const noexcept { return ::std::make_reverse_iterator(this->end()); }
const_reverse_iterator crbegin() const noexcept { return ::std::make_reverse_iterator(this->cend()); }
reverse_iterator rend() noexcept { return ::std::make_reverse_iterator(this->begin()); }
const_reverse_iterator rend() const noexcept { return ::std::make_reverse_iterator(this->begin()); }
const_reverse_iterator crend() const noexcept { return ::std::make_reverse_iterator(this->cbegin()); }
size_type size() const noexcept { return this->m_values.size(); }
bool empty() const noexcept { return this->m_values.empty(); }
reference operator[](const size_type n) {
if constexpr (has_aliases) {
return *this->m_values[n];
} else {
return this->m_values[n];
}
}
const_reference operator[](const size_type n) const {
if constexpr (has_aliases) {
return *this->m_values[n];
} else {
return this->m_values[n];
}
}
reference front() { return *this->begin(); }
const_reference front() const { return *this->begin(); }
reference back() { return *this->rbegin(); }
const_reference back() const { return *this->rbegin(); }
V operator+() const {
return *this;
}
V operator-() const {
V res = *this;
for (auto& v : res) v = -v;
return res;
}
V& operator+=(const V& other) {
assert(this->size() == other.size());
for (::std::size_t i = 0; i < this->size(); ++i) {
(*this)[i] += other[i];
}
return *this;
}
friend V operator+(const V& lhs, const V& rhs) {
return V(lhs) += rhs;
}
V& operator-=(const V& other) {
assert(this->size() == other.size());
for (::std::size_t i = 0; i < this->size(); ++i) {
(*this)[i] -= other[i];
}
return *this;
}
friend V operator-(const V& lhs, const V& rhs) {
return V(lhs) -= rhs;
}
V& operator*=(const T& c) {
for (auto& v : *this) v *= c;
return *this;
}
friend V operator*(const T& lhs, const V& rhs) {
return V(rhs) *= lhs;
}
friend V operator*(const V& lhs, const T& rhs) {
return V(lhs) *= rhs;
}
V& operator/=(const T& c) {
for (auto& v : *this) v /= c;
return *this;
}
friend V operator/(const V& lhs, const T& rhs) {
return V(lhs) /= rhs;
}
friend bool operator==(const V& lhs, const V& rhs) {
return ::std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}
friend bool operator!=(const V& lhs, const V& rhs) {
return !(lhs == rhs);
}
T inner_product(const V& other) const {
assert(this->size() == other.size());
T res{};
for (::std::size_t i = 0; i < this->size(); ++i) {
res += (*this)[i] * other[i];
}
return res;
}
T l1_norm() const {
T res{};
for (const auto& v : *this) {
res += ::tools::abs(v);
}
return res;
}
T squared_l2_norm() const {
return this->inner_product(*this);
}
F l2_norm() const {
return ::std::sqrt(static_cast<F>(this->squared_l2_norm()));
}
template <bool SFINAE = ::std::is_floating_point_v<T>, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
V normalized() const {
return *this / this->l2_norm();
}
friend ::std::ostream& operator<<(::std::ostream& os, const V& self) {
os << '(';
::std::string delimiter = "";
for (const auto& v : self) {
os << delimiter << v;
delimiter = ", ";
}
return os << ')';
}
friend ::std::istream& operator>>(::std::istream& is, V& self) {
for (auto& v : self) {
is >> v;
}
return is;
}
template <bool SFINAE = N == 2, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
T outer_product(const V& other) const {
return this->x * other.y - this->y * other.x;
}
template <bool SFINAE = N == 2, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
V turned90() const {
return V{-this->y, this->x};
}
template <bool SFINAE = N == 2, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
V turned270() const {
return V{this->y, -this->x};
}
template <bool SFINAE = N == 2, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
static const ::std::array<V, 4>& four_directions() {
static const ::std::array<V, 4> res = {
V{T(1), T(0)},
V{T(0), T(1)},
V{T(-1), T(0)},
V{T(0), T(-1)}
};
return res;
}
template <bool SFINAE = N == 2, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
static const ::std::array<V, 8>& eight_directions() {
static const ::std::array<V, 8> res = {
V{T(1), T(0)},
V{T(1), T(1)},
V{T(0), T(1)},
V{T(-1), T(1)},
V{T(-1), T(0)},
V{T(-1), T(-1)},
V{T(0), T(-1)},
V{T(1), T(-1)}
};
return res;
}
template <bool SFINAE = N == 3, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
V outer_product(const V& other) const {
return V{this->y * other.z - this->z * other.y, this->z * other.x - this->x * other.z, this->x * other.y - this->y * other.x};
}
template <bool SFINAE = N == 3 && ::std::is_floating_point_v<T>, ::std::enable_if_t<SFINAE, ::std::nullptr_t> = nullptr>
::std::array<V, 3> orthonormal_basis() const {
assert((*this != V{0, 0, 0}));
::std::array<V, 3> v;
v[0] = *this;
v[1] = V{0, this->z, -this->y};
if (v[1] == V{0, 0, 0}) {
v[1] = V{-this->z, 0, this->x};
}
v[1] -= v[0].inner_product(v[1]) / v[0].inner_product(v[0]) * v[0];
v[0] = v[0].normalized();
v[1] = v[1].normalized();
v[2] = v[0].outer_product(v[1]);
return v;
}
};
}
namespace std {
template <typename T>
struct hash<::tools::vector<T, 2>> {
using result_type = ::std::size_t;
using argument_type = ::tools::vector<T, 2>;
result_type operator()(const argument_type& key) const {
static const ::tools::tuple_hash<T, T> hasher;
return hasher(::std::make_tuple(key.x, key.y));
}
};
template <typename T>
struct hash<::tools::vector<T, 3>> {
using result_type = ::std::size_t;
using argument_type = ::tools::vector<T, 3>;
result_type operator()(const argument_type& key) const {
static const ::tools::tuple_hash<T, T, T> hasher;
return hasher(::std::make_tuple(key.x, key.y, key.z));
}
};
template <typename T>
struct hash<::tools::vector<T, 4>> {
using result_type = ::std::size_t;
using argument_type = ::tools::vector<T, 4>;
result_type operator()(const argument_type& key) const {
static const ::tools::tuple_hash<T, T, T, T> hasher;
return hasher(::std::make_tuple(key.x, key.y, key.z, key.w));
}
};
}
#line 5 "tools/vector2.hpp"
namespace tools {
template <typename T>
using vector2 = ::tools::vector<T, 2>;
}
#line 11 "tests/weighted_bipartite_matching/maximize.test.cpp"
using ll = long long;
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
ll N, M;
std::cin >> N >> M;
std::vector<std::string> S(N);
for (auto& S_i : S) std::cin >> S_i;
tools::weighted_bipartite_matching<ll> graph(N * M, N * M, true);
ll number_of_pieces = 0;
for (ll y1 = 0; y1 < N; ++y1) {
for (ll x1 = 0; x1 < M; ++x1) {
if (S[y1][x1] == 'o') {
++number_of_pieces;
std::queue<tools::vector2<ll>> queue;
queue.emplace(x1, y1);
auto will_visit = std::vector(N, std::vector(M, false));
will_visit[y1][x1] = true;
while (!queue.empty()) {
const auto here = queue.front();
queue.pop();
graph.add_edge(y1 * M + x1, here.y * M + here.x, (here.y - y1) + (here.x - x1));
if (here.y + 1 < N && !will_visit[here.y + 1][here.x] && S[here.y + 1][here.x] != '#') {
queue.emplace(here.x, here.y + 1);
will_visit[here.y + 1][here.x] = true;
}
if (here.x + 1 < M && !will_visit[here.y][here.x + 1] && S[here.y][here.x + 1] != '#') {
queue.emplace(here.x + 1, here.y);
will_visit[here.y][here.x + 1] = true;
}
}
}
}
}
std::cout << graph.query(number_of_pieces)->first << '\n';
return 0;
}