排序与链
将每个模块的候选设计按性能非递减排序,记排序后的性能和消耗量为 bi,j,ci,j。排序时必须将性能和消耗量成对移动。
di,k=bi,k+1−bi,k
为模块 i 建立 Ai−1 个顶点 v,并令 、。顶点 在源点一侧表示选择的设计编号大于 。对每个 ,加入容量为无穷大的反向边 。有限割中源点侧的顶点必定构成前缀,因此恰好割断一条正向链边。 时也可用一条 的边表示。
乘积的分解
对于一座矿山,按输入顺序将两个模块记为 u,v,选定的性能记为 Bu,Bv。
−BuB
最后一项等于 ∑k,ldu,kd。对所有 、,加入从 到 、容量为 的边。增量为 时可以省略对应边。使用相同模块对的矿山仍须逐一处理。
一元代价与答案恢复
αi=
K=1+max(0,i,jmax(−q
对每个 1≤j≤Ai,将正向边 vi 的容量设为 ,该值为正。设计选择与有限割一一对应。割容量等于净收益的相反数加上 ,因此求最小割即可。
answer=MK−mincut−k=1∑
数值范围与复杂度
答案在 −49998 到 999999998 之间。满足 αi≤10、、、。一座矿山的惩罚边容量总和为 。所有有限容量之和小于 ,因此可用 表示无穷大。所有运算均可使用有符号 位整数。
顶点数 V≤452,加入的边数 E≤82000,残量反向边另行存储。Dinic 算法的一般时间复杂度为 O(V2E),空间复杂度为 。
子任务
子任务 1 枚举所有设计组合,时间复杂度为 O((N+M)∏iAi),最多有 种组合。子任务 2 中每个模块至多只有一个二元选择,可用每个模块至多一个顶点的最小割解决。子任务 3 使用完整的链。另一份正确程序使用 的阈值展开,以交叉验证两种构造。
Solution written by GPT6