Educational Codeforces Round 108 回顾

补题链接：https://codeforces.com/contest/1519

记录

竟然足足一周没有正经的训练了…… 唉，这样可不行啊

这一场的话 ABC 肯定是没啥问题的，D 能不能做出来心里还真的没底；毕竟正式 CF 也不会允许我打了三个题然后出去吃顿饭什么的，所以只能说悬（

题解

F - Chests and Keys

有 $n$ 个宝箱，其中第 $i$ 个包含了 $a_i$ 个硬币；有 $m$ 把钥匙，其中第 $j$ 把可以卖 $b_j$ 个硬币。这些钥匙分别对应了不同种类的锁；如果要在第 $i$ 个箱子上安装可以用第 $j$ 把钥匙打开的锁，需要 $c_{i, j}$ 的成本；如果一个箱子上挂了多把锁，那么只有持有所有的这些钥匙才可以打开宝箱。
现在，Alice 持有这些宝箱和钥匙，并付出一定的成本来为箱子上锁；随后，Bob 会花一些硬币购买钥匙，并打开可以打开的所有宝箱以拿走其中的硬币；如果最后 Bob 的净利润严格大于 0，Bob 胜利；否则 Alice 胜利；现在，要求求出 Alice 必定胜利所需要付出的最少成本。
数据范围： $1\leq n, m \leq 6$ ； $1\leq a_i, b_j \leq 4$ ； $1\leq c_{i, j} \leq 10^7$ ；

只能说看到这个题目，是非常的没有想法了；但是数据又很小，像极了乱搞……那么问题就是怎么乱搞了（

首先，在解决这个问题之前，我们先解决一个经过劣化后的问题—— 如果 Alice 上锁的方式已经确定，那么 Bob 要怎么购买钥匙才能获得最大的收益呢？

为了解决这个劣化后的问题，我们对题目中描述的模型进行建模：将宝箱全部看作连接了源点的节点，且和源点连边容量为 $a_i$ ；将钥匙全部看作链接了汇点的节点，且连边的容量为 $b_j$ ；根据宝箱的上锁情况，从宝箱出发到对应的钥匙连边，边权是 $\infin$ ；这样，我们就将上面的问题变成了一个网络流的问题。

那么，这个网络流的含义是什么呢？首先，我们可以获得的最大的收益是所有箱子的硬币之和，我们所支出的成本最多是所有的钥匙的价格之和；每当上锁，我们就相当于增加一个箱子打开的门槛—— 对于一个具体的箱子，我们打开它的成本是它所使用到的锁的钥匙的价格总和，但是不超过箱子能提供的硬币数量—— 没有人会去做一件亏本的事情。初始情况下，我们可以免费打开所有的箱子，但是因为上锁，所以我们需要付出额外的成本：因此，连边就代表了上锁带来的额外成本——这个箱子的成本需要由它上的锁对应的钥匙分担；综上所述，确定了上锁方案的情况下，Bob 得到的最大收益是：

\sum_{i = 1}^n a_i - \text{maxFlow}

如果一个箱子的收益完全被需要用来开它的钥匙抵消了，那么就没有开的价值了；但是如果一把钥匙承担了超过它本身价值的收益的话，那么这把钥匙就有买的必要；一种达到这个最大收益的办法是购买所有出边满流的钥匙，但是购买的钥匙数量未必是最少的。

虽然，这种建模方法和常见的裸的网络流并不一样：因为钥匙和箱子的关系是 & 的，因此如果按照代价建模的话，网络流可以恰好地考虑到钥匙开锁的性质和成本。

但是，即使数据范围像本题这样小，上锁方案还是有 $nm$ 种；如果要枚举所有的上锁方案，其时间复杂度是 $\mathcal{O}(2^{nm})$ 的；因此，我们回到这个问题本身：注意到，如果 Bob 总是按照最大收益来进行操作的话，那么 Bob 的收益是不可能为负数的——因为 Bob 总是可以选择不购买任何钥匙，不打开任何的箱子，这样最后的总收入是 0；那么带入到上面的网络流模型中，就是所有的宝箱的价值都作为成本流量流入了汇点；换句话说，这个网络流的一个最小割是源点和其他所有节点。

那么考虑上述的网络流中没有任何上锁的连边，我们现在来考虑在这张图中连边；我们用状态 $[F_{1..n}, L, R, P]$ 来表示当前的网络流图的连边状态： $F_i$ 代表从源点到宝箱 $i$ 的连边流出的成本， $L$ 表示当前考虑的宝箱， $R$ 表示当前考虑的钥匙编号 $j$ ， $P$ 表示从钥匙 $j$ 到汇点的连边流入的成本；现在，我们考虑所有的 $i \to j$ 的连边，进行动态规划：

跳过 $i \to j$ ：也就是这条边不上锁
利用这条边转移一些成本：这条边上锁，但是转移的一部分流量

如果使用这条边转移流量，那么需要满足 $S \to i$ 和 $j \to T$ 的边都还有足够的流量剩余；更新状态之后，若所有的 $F_i$ 都已经满流了，则说明成本已经足够抵消所有的宝箱了，更新答案；同时，按照一个特定的顺序考虑 $[L, R]$ ，将下一对要考虑的点对更新到状态中。如果状态合法，就更新到 dp 数组中。

简单地说，因为数据范围小，我们枚举所有满足了约束条件的转移方法导致的状态，并计算所有的流空的状态的花费的最小值。因为流量最多为 $4$ ，而最多的情况下也只有 $36$ 条边，在考虑到每条边容量的约束条件，实际上状态数是相当有限的。

实现

一些小细节：我们考虑 $[L, R]$ 的顺序是先改变 $L$ 再改变 $R$ ，这需要体现到映射函数中。

此外，因为考虑使用边运输流量的过程，一定是 $S$ 流出的递增的过程，所以在映射函数中这一部分的值总是在最高位；

因为每次要将所有的 $[L, R]$ 的状态考虑周全，所以流出流量 $P$ 在映射函数中是最低位的。

int n, m, a[10], b[10], c[10][10];
const int F = 4e7, inf = 0x3f3f3f3f;
int dp[F];

struct state {
    vector<int> flow{};
    int lf{}, rt{}, push{};

    state() = default;
    state(const vector<int> &flow, int lf, int rt, int push)
    : flow(flow), lf(lf), rt(rt), push(push) {}
};

template <>
struct std::hash<vector<int>> :
        public __hash_base<size_t, vector<int>> {
    size_t operator()(const vector<int> &x) const noexcept {
        size_t _hashcode = 0;
        for (auto el : x) _hashcode = _hashcode * 5 + el;
        return _hashcode;
    }

    vector<int> operator[](size_t hashcode) const noexcept {
        vector<int> _ret(n);
        for (int i = n - 1; i >= 0; -- i)
            _ret[i] = int(hashcode % 5), hashcode /= 5;
        return _ret;
    }
};

template <>
struct std::hash<state> :
        public __hash_base<size_t, state> {
    size_t operator()(const state &x) const noexcept {
        size_t _hashcode = hash<vector<int>>{}(x.flow);
        _hashcode = _hashcode * 6 + x.rt;
        _hashcode = _hashcode * 6 + x.lf;
        _hashcode = _hashcode * 5 + x.push;
        return _hashcode;
    }

    state operator[](size_t hashcode) const noexcept {
        auto _push = int(hashcode % 5);
        auto _lf = int((hashcode /= 5) % 6);
        auto _rt = int((hashcode /= 6) % 6);
        return state(
                hash<vector<int>>{}[hashcode /= 6],
                _lf, _rt, _push);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    $(n, m).nextArray(a, a + n).nextArray(b, b + m);
    const vector<int> va(a, a + n), vb(b, b + m);
    for (int i = 0; i < n; ++ i)
        $.nextArray(c[i], c[i] + m);
    memset(dp, 0x3f, sizeof dp);
    int ans = inf; dp[0] = 0;
    for (int i = 0; i < F; ++ i) {
        if (dp[i] == inf) continue;
        auto s = hash<state>{}[i];
        for (auto f : {0, 1, 2, 3, 4}) {
            if (s.flow[s.lf] + f > a[s.lf] ||
                s.push + f > b[s.rt]) break;
            int pay = !f ? 0 : c[s.lf][s.rt];
            auto now = s;
            now.flow[s.lf] += f, now.push += f;
            if (s.lf + 1 == n) {
                now.lf = now.push = 0;
                now.rt = s.rt + 1;
            } else now.lf = s.lf + 1;
            if (now.flow == va) minimize(ans, dp[i] + pay);
            if (now.rt < m) {
                auto id = hash<state>{}(now);
                minimize(dp[id], dp[i] + pay);
            }
        }
    }
    $.put(ans == inf ? -1 : ans);

    return 0;
}

只能说从网络流建模，到最后的那个 DP 求解，没有一个是现在的我能想出来的（）图论，网络流，恐怖如斯——这也不是我近来第一次被网络流题目锤了== 得想点办法才行。

实际上，这个题涉及到的东西远不止这篇题解胡说八道的这么点，与之相关的知识点比想象中还是要多出许多的。

后记

没什么特别想说的，一周不写代码手感属实全无了== 实际上 E 也不算是什么难题~~虽然我也没有想到极角排序什么的~~，但是为什么每一次遇到这种题（不管是我自己打 cf 还是在线下训练中遇到了）都做的非常的费劲呢——还是做题思维的问题吧，ACM 之所以我这种人也能勉强打打，就是因为比起 OI 而言它会更加的注重思维水平；所以还是得多想多学（

此外，我的图论属实有些拉跨——这个 F 实际上还有很多关键词相关联：比如什么最大权闭合子图啊，什么霍尔定理啊，什么二分图匹配啊之类的，但是十分恐怖的是我都不会；就算是偏向思维的比赛，也是要建立在你有足够的知识积累的基础上，只能说这样属实不行（）得花个专门的时间搞搞图论才行啊 ==

Educational Codeforces Round 108 回顾

记录

题解

A - Red and Blue Beans

B - The Cake Is a Lie

C - Berland Regional

D - Maximum Sum of Products

实现

E - Off by One

实现

F - Chests and Keys

实现

后记