CF2046D 题解

· · 题解

有 n 个仓库，每个仓库中有 a_i 个机器人。你可以在最开始激活若干个仓库，这会使得其中的所有机器人被激活。被激活的机器人可以沿有向边移动，去激活沿途的仓库。问最初最少激活多少个仓库才能让所有仓库都被激活。

如果一个强连通分量内有一个仓库被激活了，则这等同于强连通分量的所有仓库都被激活了。于是可以缩点。强连通分量的点权为其中各个仓库的点权之和。

将题目转写为最大化每个点被其它仓库经过的获益和。记一个仓库 i 是被其它仓库激活的获益为 b_i。具体地，如果 a_i=0，那么 i 就必须被经过，所以可以考虑令 b_i = +\infty。否则，i 就可以不用被手动激活了，代价 -1，所以令 b_i = 1。本贡献可以拆成当 i 第一次被经过时，收益为 b_i，否则收益为 0。

于是就可以建图了：把每个点 i 拆成入点 \text{in}_i 以及出点 \text{out}_i，连接这几类边：

$(T,\text{out}_i,+\infty,0)$：结束路径。 $(\text{out}_u,\text{in}_v,+\infty,0)$：经过有向边。 $(\text{in}_i,\text{out}_i,1,b_i)$：首次有 $b_i$ 的获益。 $(\text{in}_i,\text{out}_i,+\infty,0)$ ：其余情况经过 $i$ 点没有获益。 求最大费用可行流即可。无解当且仅当存在一个 $i$ 满足 $b_i = +\infty$，有 $(\text{in}_i,\text{out}_i,1,b_i)$ 无流量。拿 $\sum b_i$ 减去最大费用即可。 由于流量至多有 $n$，每次寻找的复杂度为 $O(nm)$，所以最坏时间复杂度为 $O(n^2m)$。