cp-documentation
This documentation is automatically generated by online-judge-tools/verification-helper
競プロ典型90問-040 Get More Money
(Test/Manual/typical90_an.test.cpp)
- View this file on GitHub
- Last update: 2024-01-26 17:02:26+09:00
- Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
- Link: https://atcoder.jp/contests/typical90/submissions/49664834
燃やす埋める
$x_{i} =$ 家 $i$ に入る時 $1$ 、家 $i$ に入らない時 $0$ とする。
$x_{i}$ の割り当て方によって以下の様に利得が発生する。
- $x_{i} = 1$ ならば、 $W - A_{i}$ 円の得
- $x_{i} = 0$ かつ $x_{c_{ij}} = 1$ ならば、 $-\infty$ 円の得(このような割り当ての禁止)
- $x_{1}, x_{2}, \dots, x_{n}$ に $01$ を上手く割り当てて得られるお金の総和を最大化したい
最小カットに帰着したいので、全て $-1$ 倍することで最小化問題を考えることにする。
- $x_{i} = 1$ ならば、 $-(W - A_{i})$ 円の損
- $x_{i} = 0$ かつ $x_{c_{ij}} = 1$ ならば、 $\infty$ 円の損(このような割り当ての禁止)
- $x_{1}, x_{2}, \dots, x_{n}$ に $01$ を上手く割り当てて損失するお金の総和を最小化したい
二番目の条件が $2$ 変数関数になっているので、劣モジュラ性を持つかを確認する必要がある。
| $i \ c_{ij}$ | 0 | 1 |
|---|---|---|
| 0 | 0 | $\infty$ |
| 1 | 0 | 0 |
$i\ \lt\ j, x_{i} = 0, x_{j} = 1$ の数を $\text{cnt}$ として $S = (x_{1}, x_{2}, \dots, x_{n})$ $T = (x_{1}’, x_{2}’, \dots, x_{n}’)$
$S\cap T, S\cup T$ との $\text{cnt}$ の変化を考えると、 $\text{cnt}(S) + \text{cnt}(T) = \text{cnt}(S\cap T) + \text{cnt}(S\cup T)$ なので劣モジュラ性が成り立っている。
Depends on
- Src/Graph/Flow/BurnBury.hpp
- Dinic (最大流・最小カット)
(Src/Graph/Flow/Dinic.hpp)
- ioまわりの設定
(Src/Template/IOSetting.hpp)
- 標準データ型のエイリアス
(Src/Template/TypeAlias.hpp)
- Src/Utility/U32Pair.hpp
Code
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"
#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Graph/Flow/BurnBury.hpp"
#include <iostream>
/*
* 競プロ典型90問-040 Get More Money
* https://atcoder.jp/contests/typical90/submissions/49664834
*/
void solve() {
using namespace zawa;
SetFastIO();
int n; std::cin >> n;
BurnBury<long long> solver(n);
long long w; std::cin >> w;
for (int i{} ; i < n ; i++) {
long long a; std::cin >> a;
solver.func1(i, { 0LL, -(a - w) });
}
const long long INF{(long long)1e12};
for (int i{} ; i < n ; i++) {
int k; std::cin >> k;
for (int _{} ; _ < k ; _++) {
int c; std::cin >> c;
c--;
solver.func2(i, c, { 0LL, INF, 0LL, 0LL });
}
}
long long ans{solver.build()};
ans *= -1;
std::cout << ans << '\n';
}
int main() {
#ifdef ATCODER
solve();
#else
std::cout << "Hello World" << '\n';
#endif
}#line 1 "Test/Manual/typical90_an.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"
#line 2 "Src/Template/IOSetting.hpp"
#line 2 "Src/Template/TypeAlias.hpp"
#include <cstdint>
#include <cstddef>
namespace zawa {
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;
using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using usize = std::size_t;
} // namespace zawa
#line 4 "Src/Template/IOSetting.hpp"
#include <iostream>
#include <iomanip>
namespace zawa {
void SetFastIO() {
std::cin.tie(nullptr)->sync_with_stdio(false);
}
void SetPrecision(u32 dig) {
std::cout << std::fixed << std::setprecision(dig);
}
} // namespace zawa
#line 2 "Src/Graph/Flow/BurnBury.hpp"
#line 2 "Src/Utility/U32Pair.hpp"
#line 4 "Src/Utility/U32Pair.hpp"
#include <functional>
#line 7 "Src/Utility/U32Pair.hpp"
namespace zawa {
class U32Pair {
private:
static constexpr u32 SHIFT{32};
static constexpr u32 MASK{static_cast<u32>((1LL << SHIFT) - 1)};
u64 value_{};
public:
constexpr U32Pair() {}
constexpr U32Pair(u32 first, u32 second) {
value_ = (static_cast<u64>(first) << SHIFT) | second;
}
constexpr u32 first() const noexcept {
return static_cast<u32>(value_ >> SHIFT);
}
constexpr u32 second() const noexcept {
return static_cast<u32>(value_ & MASK);
}
constexpr u64 combined() const noexcept {
return value_;
}
constexpr U32Pair& operator=(const U32Pair& rhs) {
value_ = rhs.value_;
return *this;
}
friend constexpr bool operator==(const U32Pair& lhs, const U32Pair& rhs) {
return lhs.value_ == rhs.value_;
}
friend constexpr bool operator!=(const U32Pair& lhs, const U32Pair& rhs) {
return lhs.value_ != rhs.value_;
}
friend constexpr bool operator<(const U32Pair& lhs, const U32Pair& rhs) {
return lhs.value_ < rhs.value_;
}
friend constexpr bool operator<=(const U32Pair& lhs, const U32Pair& rhs) {
return lhs.value_ <= rhs.value_;
}
friend constexpr bool operator>(const U32Pair& lhs, const U32Pair& rhs) {
return lhs.value_ > rhs.value_;
}
friend constexpr bool operator>=(const U32Pair& lhs, const U32Pair& rhs) {
return lhs.value_ >= rhs.value_;
}
friend std::ostream& operator<<(std::ostream& os, const U32Pair& pair) {
os << '(' << pair.first() << ',' << pair.second() << ')';
return os;
}
};
struct U32PairHash {
usize operator()(const U32Pair& pair) const noexcept {
return std::hash<u64>{}(pair.combined());
}
};
} // namespace zawa
#line 2 "Src/Graph/Flow/Dinic.hpp"
#line 5 "Src/Graph/Flow/Dinic.hpp"
#include <algorithm>
#include <cassert>
#include <limits>
#include <type_traits>
#include <vector>
#include <queue>
namespace zawa {
template <class Cap>
class Dinic {
private:
static_assert(std::is_signed_v<Cap>, "Cap must be signed");
usize n_{}, m_{};
static constexpr u32 invalid() noexcept {
return std::numeric_limits<u32>::max();
}
public:
inline usize size() const noexcept {
return n_;
}
inline usize edgeNumber() const noexcept {
return m_;
}
private:
struct Edge {
u32 to{}, rev{};
Cap residual{};
Edge() = default;
Edge(u32 to, u32 rev, const Cap& residual)
: to{to}, rev{rev}, residual{residual} {}
};
std::vector<std::vector<Edge>> g_;
std::vector<U32Pair> edges_;
std::vector<u32> label_, cur_;
bool dualStep(u32 s, u32 t) {
std::fill(label_.begin(), label_.end(), invalid());
label_[s] = 0;
std::queue<u32> queue{ { s } };
while (queue.size()) {
u32 v{queue.front()};
queue.pop();
for (const Edge& e : g_[v]) if (e.residual > 0) {
if (label_[e.to] > label_[v] + 1) {
label_[e.to] = label_[v] + 1;
if (e.to == t) return true;
queue.emplace(e.to);
}
}
}
return false;
}
bool admissible(u32 v, const Edge& e) const noexcept {
return e.residual > 0 and label_[v] + 1 == label_[e.to];
}
inline void flow(Edge& e, Cap f) {
e.residual -= f;
g_[e.to][e.rev].residual += f;
}
Cap dfs(u32 v, u32 t, Cap up) {
if (v == t) return up;
Cap res{};
for (u32& i{cur_[v]} ; i < g_[v].size() ; i++) {
if (!admissible(v, g_[v][i])) continue;
Cap f{dfs(g_[v][i].to, t, std::min(g_[v][i].residual, up - res))};
if (f == 0) continue;
flow(g_[v][i], f);
res += f;
if (res == up) return res;
}
return res;
}
Cap primalStep(u32 s, u32 t) {
std::fill(cur_.begin(), cur_.end(), 0u);
cur_[t] = g_[t].size();
Cap res{};
while (true) {
Cap f{dfs(s, t, std::numeric_limits<Cap>::max())};
if (f == 0) break;
res += f;
}
return res;
}
const Edge& edge(u32 i) const noexcept {
return g_[edges_[i].first()][edges_[i].second()];
}
const Edge& reverse(u32 i) const noexcept {
const Edge& e{edge(i)};
return g_[e.to][e.rev];
}
public:
Dinic() = default;
Dinic(u32 n, u32 m = 0u)
: n_{n}, m_{m}, g_(n), edges_{}, label_(n), cur_(n) {
g_.shrink_to_fit();
label_.shrink_to_fit();
cur_.shrink_to_fit();
edges_.reserve(m);
}
u32 addEdge(u32 u, u32 v, const Cap& cap) {
assert(u < size());
assert(v < size());
u32 id{static_cast<u32>(g_[u].size())};
u32 revId{u == v ? id + 1 : static_cast<u32>(g_[v].size())};
u32 res{static_cast<u32>(edges_.size())};
edges_.emplace_back(u, id);
g_[u].emplace_back(v, revId, cap);
g_[v].emplace_back(u, id, Cap{});
m_++;
return res;
}
const Cap& flowed(u32 id) const noexcept {
assert(id < edgeNumber());
return reverse(id).residual;
}
const Cap& residual(u32 id) const noexcept {
assert(id < edgeNumber());
return edge(id).residual;
}
const Cap& capacity(u32 id) const noexcept {
assert(id < edgeNumber());
return edge(id).residual + reverse(id).residual;
}
const u32& from(u32 id) const noexcept {
assert(id < edgeNumber());
return edges_[id].first();
}
const u32& to(u32 id) const noexcept {
assert(id < edgeNumber());
return edge(id).to;
}
Cap flow(u32 s, u32 t) {
assert(s < size());
assert(t < size());
Cap res{};
while (dualStep(s, t)) {
res += primalStep(s, t);
}
return res;
}
std::vector<bool> cut(u32 s) {
std::vector<bool> res(size());
res[s] = true;
std::queue<u32> queue{ { s } };
while (queue.size()) {
u32 v{queue.front()};
queue.pop();
for (const auto& e : g_[v]) if (e.residual > 0 and !res[e.to]) {
res[e.to] = true;
queue.emplace(e.to);
}
}
return res;
}
};
} // namespace zawa
#line 6 "Src/Graph/Flow/BurnBury.hpp"
#line 8 "Src/Graph/Flow/BurnBury.hpp"
#include <unordered_map>
#line 10 "Src/Graph/Flow/BurnBury.hpp"
namespace zawa {
template <class Cost>
class BurnBury {
private:
usize n_{}, source_{}, sink_{}, graphsize_{};
Dinic<Cost> mf_{};
Cost common_{};
std::unordered_map<U32Pair, Cost, U32PairHash> edge_{};
void addEdge(u32 u, u32 v, const Cost& cost) {
edge_[U32Pair{ u, v }] += cost;
}
constexpr usize size() const noexcept {
return n_;
}
public:
BurnBury() = default;
BurnBury(usize n) : n_{n}, source_{n}, sink_{n + 1}, graphsize_{n + 2} {
assert(n);
}
void constant(const Cost& cost) {
common_ += cost;
}
void func1(u32 v, const std::vector<Cost>& cost) {
assert(v < size());
assert(cost.size() == (1u << 1));
if (cost[0] <= cost[1]) {
addEdge(source_, v, cost[1] - cost[0]);
constant(cost[0]);
}
else {
addEdge(v, sink_, cost[0] - cost[1]);
constant(cost[1]);
}
}
void func2(u32 u, u32 v, const std::vector<Cost>& cost) {
assert(u < size());
assert(v < size());
assert(cost.size() == (1u << 2));
constant(cost[0]);
func1(u, { Cost{0}, cost[2] - cost[0] });
func1(v, { Cost{0}, cost[3] - cost[2] });
assert(cost[1] + cost[2] - cost[0] - cost[3] >= 0);
addEdge(u, v, cost[1] + cost[2] - cost[0] - cost[3]);
}
void func3(u32 u, u32 v, u32 w, const std::vector<Cost>& cost) {
assert(u < size());
assert(v < size());
assert(w < size());
assert(cost.size() == (1u << 3));
Cost p{cost[1] + cost[3] + cost[5] + cost[6] - (cost[1] + cost[2] + cost[4] + cost[7])};
if (p >= 0) {
constant(cost[0]);
func1(u, Cost{0}, cost[5] - cost[1]);
func1(v, Cost{0}, cost[6] - cost[4]);
func1(w, Cost{0}, cost[3] - cost[2]);
// 01以外は0
func2(u, v, { Cost{0}, cost[2] + cost[4] - cost[0] - cost[6], Cost{0}, Cost{0} });
func2(v, w, { Cost{0}, cost[1] + cost[2] - cost[0] - cost[3], Cost{0}, Cost{0} });
func2(w, u, { Cost{0}, cost[1] + cost[4] - cost[0] - cost[5], Cost{0}, Cost{0} });
// 111とすると-p
addEdge(u, graphsize_, p);
addEdge(v, graphsize_, p);
addEdge(w, graphsize_, p);
addEdge(graphsize_, sink_, p);
constant(-p);
graphsize_++;
}
else {
constant(cost[7]);
func1(u, { cost[2] - cost[6], Cost{0} });
func1(v, { cost[1] - cost[3], Cost{0} });
func1(w, { cost[4] - cost[5], Cost{0} });
// 10の時
func2(u, v, { Cost{0}, Cost{0}, cost[3] + cost[5] - cost[1] - cost[7], Cost{0} });
func2(v, w, { Cost{0}, Cost{0}, cost[5] + cost[6] - cost[4] - cost[7], Cost{0} });
func2(w, u, { Cost{0}, Cost{0}, cost[3] + cost[6] - cost[2] - cost[7], Cost{0} });
// 000
addEdge(source_, graphsize_, -p);
addEdge(graphsize_, u, -p);
addEdge(graphsize_, v, -p);
addEdge(graphsize_, w, -p);
constant(p);
graphsize_++;
}
}
[[nodiscard]] Cost build() {
mf_ = Dinic<Cost>(graphsize_);
for (const auto& [uv, cost] : edge_) {
mf_.addEdge(uv.first(), uv.second(), cost);
}
Cost res{mf_.flow(source_, sink_)};
res += common_;
return res;
}
[[nodiscard]] std::vector<u32> assign() {
auto tos{mf_.cut(source_)}, tot{mf_.cut(sink_)};
std::vector<u32> res(size());
for (u32 i{} ; i < size() ; i++) {
if (!tos[i] and !tot[i]) res[i] = 2;
else if (tos[i]) res[i] = 0;
else res[i] = 1;
}
return res;
}
};
} // namespace zawa
#line 5 "Test/Manual/typical90_an.test.cpp"
#line 7 "Test/Manual/typical90_an.test.cpp"
/*
* 競プロ典型90問-040 Get More Money
* https://atcoder.jp/contests/typical90/submissions/49664834
*/
void solve() {
using namespace zawa;
SetFastIO();
int n; std::cin >> n;
BurnBury<long long> solver(n);
long long w; std::cin >> w;
for (int i{} ; i < n ; i++) {
long long a; std::cin >> a;
solver.func1(i, { 0LL, -(a - w) });
}
const long long INF{(long long)1e12};
for (int i{} ; i < n ; i++) {
int k; std::cin >> k;
for (int _{} ; _ < k ; _++) {
int c; std::cin >> c;
c--;
solver.func2(i, c, { 0LL, INF, 0LL, 0LL });
}
}
long long ans{solver.build()};
ans *= -1;
std::cout << ans << '\n';
}
int main() {
#ifdef ATCODER
solve();
#else
std::cout << "Hello World" << '\n';
#endif
}