CF1519F Chests and Keys 题解

· · 题解

题意

有 n 个宝箱，m 种钥匙，第 i 个宝箱中有 a_i 金币，获取第 j 个钥匙需要 b_j 金币，第 j 个钥匙能开第 j 种锁。一个宝箱上可以有多道锁，打开这个宝箱需要拥有每一道锁对应的钥匙。现在另一个人需要给这些宝箱上锁，给第 i 个宝箱上第 j 种锁需要 c_{i,j} 块钱，问至少需要用多少块钱给宝箱上锁，才能让第一个人无论怎么操作花费的金币数量都大于等于从宝箱中获得的金币数量。数据范围 n,m≤6，a_i, b_i≤4。

思路

首先，形式化描述，我们需要以下条件成立：设 L_x 为第 x 个宝箱上所有的锁的集合，则对于每个宝箱集合 S，都要满足：

\sum_{i\in S}a_i\le \sum_{j\in (\bigcup_{i\in S}L_i )}b_j

这个式子的形式长得很像霍尔定理，所以考虑将原问题转化为二分图匹配的问题。

对于每个宝箱 i，将这个宝箱拆成 a_i 个点，同时，对于每个锁，将这个锁拆成 b_i 个点，如果宝箱 i 上有锁 j，则将宝箱 i 拆出的所有点连一条边到锁 j 拆出的所有点，得到一个二分图，其中宝箱拆成的点在二分图的左部，则要求这个图的左部存在完美匹配（即左部每个点都能和右部的一个点匹配，且匹配点互不相同），下面只需要构造出这个完美匹配即可。

考虑 dp：设 f(i,mask) 表示考虑到第 i 个宝箱拆成的点，右部每个锁拆成的点中还没被匹配的个数（按照五进制压缩成 mask），最少需要花费的钱是多少。转移的时候，枚举当前宝箱对应的每一个点都匹配上了哪个锁拆成的点，如果匹配上了至少一个锁 j 拆成的点，则花费的钱需要加上 c_{i,j} 。最后，取 f(n, *) 的最小值即为答案。

时间复杂度 \mathcal O(n⋅5^{2n})，常数非常小，可以通过。

代码

#include <bits/stdc++.h>
using namespace std;
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define loop(i, a) for (int i = 0; i < (a); ++i)
#define cont(i, a) for (int i = 1; i <= (a); ++i)
#define circ(i, a, b) for (int i = (a); i <= (b); ++i)
#define range(i, a, b, c) for (int i = (a); (c) > 0 ? i <= (b) : i >= (b); i += (c))
#define parse(it, x) for (auto &it : (x))
#define pub push_back
#define pob pop_back
#define emb emplace_back
#define mak make_pair
#define mkt make_tuple
typedef long long ll;
typedef long double lf;
const int Inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;

const int maxk = 20005;
int n, m;
int a[7], b[7];
int c[7][7];
int dp[7][maxk];
int mii[7];

vector<int> inline decode(int x) {
    vector<int> res;
    loop(i, m) res.pub(x % 5), x /= 5;
    return res;
}

int inline encode(const vector<int> &x) {
    int res = 0;
    range(i, m - 1, 0, -1) res = res * 5 + x[i];
    return res;
}

void inline dfs(int i, vector<int> arr, int val, int now, int cst, int rem) {
    if (now == m) {
        if (rem) return;
        int id = encode(arr);
        dp[i + 1][id] = min(dp[i + 1][id], val + cst);
        return;
    }
    dfs(i, arr, val, now + 1, cst, rem);
    loop(j, min(arr[now], rem) + 1) {
        arr[now] -= j;
        dfs(i, arr, val, now + 1, cst + c[i][now], rem - j);
        arr[now] += j;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    loop(i, n) scanf("%d", a + i);
    loop(i, m) scanf("%d", b + i);
    loop(i, n) loop(j, m) scanf("%d", c[i] + j);
    mii[0] = 1;
    cont(i, m) mii[i] = 5 * mii[i - 1];
    int ini = encode(vector<int>(b, b + m));
    memset(dp, Inf, sizeof(dp));
    dp[0][ini] = 0;
    loop(i, n) loop(j, mii[m]) {
        if (dp[i][j] >= Inf) continue;
        vector<int> arr = decode(j);
        dfs(i, arr, dp[i][j], 0, 0, a[i]);
    }
    int ans = *min_element(dp[n], dp[n] + maxk);
    printf("%d\n", ans == Inf ? -1 : ans);
    return 0;
}

本题解写于 OneNote，手动转换为 Markdown，如有格式问题请立即指出，谢谢。