#line 1 "test/aoj/2903/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2903"
#include <iostream>
#include <string>
#include <vector>
#line 2 "Mylib/Graph/Flow/ford_fulkerson.cpp"
#include <algorithm>
#include <cassert>
#line 5 "Mylib/Graph/Flow/ford_fulkerson.cpp"
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/project_selection_problem.cpp"
#include <limits>
#include <tuple>
#include <utility>
#line 7 "Mylib/Graph/project_selection_problem.cpp"
namespace haar_lib {
template <typename T, typename Flow>
class project_selection_problem {
int N_, s_, t_;
std::vector<std::tuple<int, int, T>> g_;
T default_gain_;
int nodes_;
constexpr static T INF = std::numeric_limits<T>::max();
public:
project_selection_problem() {}
project_selection_problem(int N) : N_(N), s_(N), t_(N + 1), default_gain_(0), nodes_(N + 2) {}
void penalty_if_red(int i, T c) {
assert(c >= 0);
assert(0 <= i and i < N_);
g_.emplace_back(i, t_, c);
}
void gain_if_red(int i, T c) {
assert(c >= 0);
assert(0 <= i and i < N_);
default_gain_ += c;
penalty_if_blue(i, c);
}
void penalty_if_blue(int i, T c) {
assert(c >= 0);
assert(0 <= i and i < N_);
g_.emplace_back(s_, i, c);
}
void gain_if_blue(int i, T c) {
assert(c >= 0);
assert(0 <= i and i < N_);
default_gain_ += c;
penalty_if_red(i, c);
}
void penalty_if_red_blue(int i, int j, T c) {
assert(c >= 0);
assert(0 <= i and i < N_);
assert(0 <= j and j < N_);
g_.emplace_back(i, j, c);
}
void penalty_if_different(int i, int j, T c) {
assert(c >= 0);
assert(0 <= i and i < N_);
assert(0 <= j and j < N_);
g_.emplace_back(i, j, c);
g_.emplace_back(j, i, c);
}
void must_be_red(int i) {
assert(0 <= i and i < N_);
penalty_if_blue(i, INF);
}
void must_be_blue(int i) {
assert(0 <= i and i < N_);
penalty_if_red(i, INF);
}
void if_red_then_must_be_red(int i, int j) {
assert(0 <= i and i < N_);
assert(0 <= j and j < N_);
penalty_if_red_blue(i, j, INF);
}
void gain_if_red_red(int i, int j, T c) {
assert(c >= 0);
assert(0 <= i and i < N_);
assert(0 <= j and j < N_);
default_gain_ += c;
int w = nodes_++;
g_.emplace_back(s_, w, c);
g_.emplace_back(w, i, INF);
g_.emplace_back(w, j, INF);
}
void gain_if_blue_blue(int i, int j, T c) {
assert(c >= 0);
assert(0 <= i and i < N_);
assert(0 <= j and j < N_);
default_gain_ += c;
int w = nodes_++;
g_.emplace_back(w, t_, c);
g_.emplace_back(i, w, INF);
g_.emplace_back(j, w, INF);
}
T solve() {
Flow flow(nodes_);
for (auto [i, j, w] : g_) flow.add_edge(i, j, w);
return default_gain_ - flow.max_flow(s_, t_);
}
};
} // 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 9 "test/aoj/2903/main.test.cpp"
namespace hl = haar_lib;
int main() {
int R, C;
std::cin >> R >> C;
auto S = hl::input_vector<std::string>(R);
hl::project_selection_problem<int, hl::ford_fulkerson<int>> psp(R * C);
// red: horizontal
// blue: vertical
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
if (S[i][j] == '#') {
int k = i * C + j;
psp.penalty_if_red(k, 1);
psp.penalty_if_blue(k, 1);
}
}
}
for (int i = 1; i < R; ++i) {
for (int j = 0; j < C; ++j) {
if (S[i][j] == '#' and S[i - 1][j] == '#') {
psp.gain_if_blue_blue(i * C + j, (i - 1) * C + j, 1);
}
}
}
for (int i = 0; i < R; ++i) {
for (int j = 1; j < C; ++j) {
if (S[i][j] == '#' and S[i][j - 1] == '#') {
psp.gain_if_red_red(i * C + j, i * C + (j - 1), 1);
}
}
}
auto ans = -psp.solve();
std::cout << ans << std::endl;
return 0;
}
test/aoj/2903/main.test.cpp
Ford-Fulkerson algorithm
(Mylib/Graph/Flow/ford_fulkerson.cpp)