专栏文章

CF2046D 题解

sshiruoyu114514
CF2046D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip8sojj
此快照首次捕获于
2025/12/03 08:02
3 个月前
此快照最后确认于
2025/12/03 08:02
3 个月前
查看原文
有 nn 个仓库，每个仓库中有 aia_i 个机器人。你可以在最开始激活若干个仓库，这会使得其中的所有机器人被激活。被激活的机器人可以沿有向边移动，去激活沿途的仓库。问最初最少激活多少个仓库才能让所有仓库都被激活。
如果一个强连通分量内有一个仓库被激活了，则这等同于强连通分量的所有仓库都被激活了。于是可以缩点。强连通分量的点权为其中各个仓库的点权之和。
将题目转写为最大化每个点被其它仓库经过的获益和。记一个仓库 ii 是被其它仓库激活的获益为 bib_i。具体地，如果 ai=0a_i=0，那么 ii 就必须被经过，所以可以考虑令 bi=+∞b_i = +\infty。否则，ii 就可以不用被手动激活了，代价 −1-1，所以令 bi=1b_i = 1。本贡献可以拆成当 ii 第一次被经过时，收益为 bib_i，否则收益为 00。
于是就可以建图了：把每个点 ii 拆成入点 ini\text{in}_i 以及出点 outi\text{out}_i，连接这几类边：
(S,outi,ai,0)(S,\text{out}_i,a_i,0)：只能有 aia_i 个路径以 ii 为端点。
(T,outi,+∞,0)(T,\text{out}_i,+\infty,0)：结束路径。
(outu,inv,+∞,0)(\text{out}_u,\text{in}_v,+\infty,0)：经过有向边。
(ini,outi,1,bi)(\text{in}_i,\text{out}_i,1,b_i)：首次有 bib_i 的获益。
(ini,outi,+∞,0)(\text{in}_i,\text{out}_i,+\infty,0) ：其余情况经过 ii 点没有获益。
求最大费用可行流即可。无解当且仅当存在一个 ii 满足 bi=+∞b_i = +\infty，有 (ini,outi,1,bi)(\text{in}_i,\text{out}_i,1,b_i) 无流量。拿 ∑bi\sum b_i 减去最大费用即可。
由于流量至多有 nn，每次寻找的复杂度为 O(nm)O(nm)，所以最坏时间复杂度为 O(n2m)O(n^2m)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...