加权多机区间调度

把带权区间分配到 m 台相同机器,使同一机器上区间不重叠且总权值最大;用最小费用最大流求解。

标签 最小费用最大流 / 区间 / 调度

题目描述

给定 𝑛 个区间 [𝑙𝑖,𝑟𝑖] 和权值 𝑤𝑖>0,以及 𝑚 台相同的机器。

选择若干区间并分配到机器上,使同一台机器上的区间两两不重叠,且选中区间的总权值最大。

端点相接视为相容。

题解

把所有端点离散化,按时间顺序建一条链。相邻时间点之间连容量为 𝑚、费用为 0 的边;每个区间 [𝑙𝑖,𝑟𝑖] 从 𝑙𝑖 对应的结点向 𝑟𝑖 对应的结点连容量为 1、费用为 −𝑤𝑖 的边。源点连最左端,最右端连汇点,跑流量为 𝑚 的最小费用流。

一条从源点到汇点的流对应一台机器的时间线。流过区间边表示该机器选择这个区间;区间边容量为 1,保证一个区间至多被一台机器选择;链边容量为 𝑚,保证任意时刻至多 𝑚 个区间同时进行。最小费用的相反数就是最大总权值。

费用为负,初次可使用 SPFA/Bellman–Ford,之后用势能 + Dijkstra 做连续最短路增广。

复杂度

离散化后有 𝑂(𝑛) 个结点和边。进行 𝑚 次增广,每次最短路为 𝑂(𝑛log𝑛),总时间为 𝑂(𝑚𝑛log𝑛),空间为 𝑂(𝑛)。

参考

源码位置