Problem Statement
Alice and Bob play a game. Alice has got $n$ treasure chests (the $i$-th of which contains $a_i$ coins) and $m$ keys (the $j$-th of which she can sell Bob for $b_j$ coins).
Firstly, Alice puts some locks on the chests. There are $m$ types of locks, the locks of the $j$-th type can only be opened with the $j$-th key. To put a lock of type $j$ on the $i$-th chest, Alice has to pay $c_{i,j}$ dollars. Alice can put any number of different types of locks on each chest (possibly, zero).
Then, Bob buys some of the keys from Alice (possibly none, possibly all of them) and opens each chest he can (he can open a chest if he has the keys for all of the locks on this chest). Bob's profit is the difference between the total number of coins in the opened chests and the total number of coins he spends buying keys from Alice. If Bob's profit is strictly positive (greater than zero), he wins the game. Otherwise, Alice wins the game.
Alice wants to put some locks on some chests so no matter which keys Bob buys, she always wins (Bob cannot get positive profit). Of course, she wants to spend the minimum possible number of dollars on buying the locks. Help her to determine whether she can win the game at all, and if she can, how many dollars she has to spend on the locks.
Editorial
The first thing we need to consider is that how to compute Bob's profit after Alice has locked all the chests she wants to lock.
We can build a network flow model: treat each chest as a node, then connect the source to it with an edge of capacity $a_i$; treat each lock as a node as well, then connect it to the sink with an edge of capacity $b_j$. If Alice puts a lock of $j$-th type on the $i$-th chest, then we add an edge from chest $i$ to lock $j$ with infinite capacity.
Bob's profit will be $\sum a_i - \texttt{mincut}$. The reasoning is as follows. Consider a lock of the $j$-th type on the $i$-th chest. We can either choose to cut the edge from the source to the $i$-th chest, or cut the edge from the $j$-th lock to the sink. If we choose the former, it means we have abandoned the $i$-th chest, and we added $\sum a_i$ to offset this costs; otherwise, we buy the key of $j$-th type, and obtain $a_i$ coins, so we also added $\sum a_i$.
However, we cannot enumerate all possible decisions of Alice by brute force. Upon closer inspection, we will discover that if Bob's profit is zero, then in the network graph it is equivalent to cutting all chest edges to separate the sink from all other points.
Therefore, we can use dynamic programming to simulate the flow. Use $F\left(f_1, f_2, \cdots, f_n, c, l, f\right)$ to represent the minimal cost for Alice when the flow on the edge from the source to the $i$-th chest is $f_i$, and the edge between the $c$-th chest and the $l$-th lock is being considered, and the flow from the sink to the current chest is $r$. Enumerate all possible flow to do transitions.
Code
struct SNOWFLAKE {
static constexpr char FIO_[] = "";
static constexpr char FIN_[] = "";
static constexpr char FOUT_[] = "";
static constexpr bool MTS = false;
static constexpr bool SPC_MTS = false;
template <typename Ty>
using vla = std::vector<Ty>;
template <typename Ty1, typename Ty2>
using pair = std::pair<Ty1, Ty2>;
using string = std::string;
using ll = long long int;
using ull = unsigned long long int;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vb = vla<bool>;
using vi = vla<int>;
using vl = vla<ll>;
static constexpr int INF32 = 0x3ffffffe;
static constexpr ll INF64 = 0x3ffffffffffffffe;
template <typename Ty1, typename Ty2>
static void ckmin(Ty1& x, Ty2 y) { if (y < x) x = y; }
template <typename Ty1, typename Ty2>
static void ckmax(Ty1& x, Ty2 y) { if (x < y) x = y; }
struct {
template <typename Ty>
operator Ty() { Ty x; std::cin >> x; return x; }
} reed;
template <typename Ty = int>
vla<Ty> rva(int n) {
vla<Ty> a(n);
for (auto& i : a) i = reed;
return a;
}
SNOWFLAKE() {
if (strlen(FIO_) != 0) {
freopen((std::string(FIO_) + ".in").c_str(), "r", stdin);
freopen((std::string(FIO_) + ".out").c_str(), "w", stdout);
} else {
if (strlen(FIN_) != 0) freopen(FIN_, "r", stdin);
if (strlen(FOUT_) != 0) freopen(FOUT_, "w", stdout);
}
std::cin.tie(nullptr)->sync_with_stdio(false);
}
~SNOWFLAKE() {
int t = MTS && !SPC_MTS ? reed : 1;
for (int i = 0; i < t || SPC_MTS; ++i) {
if (main(i) != 0) return;
}
}
struct {
std::unordered_map<int, int> enc;
std::unordered_map<int, vi> dec;
int HSH(vi s) {
int hsh = 0;
for (auto i : s) hsh = hsh * 6 + i;
return hsh;
}
int ENC(vi s) {
int hsh = HSH(s);
if (!enc.contains(hsh)) {
dec[enc.size()] = s;
enc[hsh] = enc.size();
}
return enc[hsh];
}
vi DEC(int hsh) { return dec[hsh]; }
} codec;
int main([[maybe_unused]] int TNO) {
int n = reed;
int m = reed;
vi a = rva(n);
vi b = rva(m);
vla<vi> c(n);
for (auto& i : c) i = rva(m);
vi f(3e6, INF32);
f[codec.ENC(vi(n + 3, 0))] = 0;
int tar = INF32;
for (int i = 0; i < f.size(); ++i) {
if (f[i] == INF32) continue;
vi s = codec.DEC(i);
int r = s.back(); s.pop_back();
int lock = s.back(); s.pop_back();
int chest = s.back(); s.pop_back();
for (int j = 0; j <= 4; ++j) {
if (s[chest] + j > a[chest] || r + j > b[lock]) break;
vi cur = s;
int $r = r;
int $chest = chest;
int $lock = lock;
int cost = j == 0 ? 0 : c[chest][lock];
cur[chest] += j;
if (codec.HSH(cur) == codec.HSH(a)) ckmin(tar, f[i] + cost);
if (chest == n - 1) {
++$lock;
$chest = 0;
$r = 0;
} else {
++$chest;
$r += j;
}
if ($lock < m) {
cur.push_back($chest);
cur.push_back($lock);
cur.push_back($r);
ckmin(f[codec.ENC(cur)], f[i] + cost);
}
}
}
std::cout << (tar == INF32 ? -1 : tar) << "\n";
return 0;
}
} SNOWFLAKE;- Category: 做题笔记
- Last update: 2025-10-05 17:35:34UTC+8
- Tags: Dynamic Programming Flows