#line 1 "test/aoj/3058/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3058"
#include <iostream>
#include <string>
#include <utility>
#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>
#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 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 6 "Mylib/IO/input_tuple.cpp"
namespace haar_lib {
template <typename T, size_t... I>
static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
}
template <typename T, typename U>
std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
s >> value.first >> value.second;
return s;
}
template <typename... Args>
std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
return s;
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuples {
struct iter {
using value_type = std::tuple<Args...>;
value_type value;
bool fetched = false;
int N, c = 0;
value_type operator*() {
if (not fetched) {
std::cin >> value;
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuples(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples(int N) {
return InputTuples<Args...>(N);
}
} // 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 11 "test/aoj/3058/main.test.cpp"
namespace hl = haar_lib;
int main() {
int N, M;
std::cin >> N >> M;
std::string U;
std::cin >> U;
auto A = hl::input_vector<int>(N);
hl::project_selection_problem<int, hl::ford_fulkerson<int>> psp(N);
// red: right, blue: left
for (int i = 0; i < N; ++i) {
if (U[i] == 'R') {
psp.penalty_if_blue(i, A[i]);
} else {
psp.penalty_if_red(i, A[i]);
}
}
for (auto [s, t, b] : hl::input_tuples<int, int, int>(M)) {
--s, --t;
if (s > t) std::swap(s, t);
psp.penalty_if_red_blue(s, t, b);
}
auto ans = -psp.solve();
std::cout << ans << std::endl;
return 0;
}
test/aoj/3058/main.test.cpp
Ford-Fulkerson algorithm
(Mylib/Graph/Flow/ford_fulkerson.cpp)