加权多机区间调度
把带权区间分配到 m 台相同机器,使同一机器上区间不重叠且总权值最大;用最小费用最大流求解。标签 最小费用最大流 / 区间 / 调度
题目描述
给定 个区间 和权值 ,以及 台相同的机器。
选择若干区间并分配到机器上,使同一台机器上的区间两两不重叠,且选中区间的总权值最大。
端点相接视为相容。
题解
把所有端点离散化,按时间顺序建一条链。相邻时间点之间连容量为 、费用为 的边;每个区间 从 对应的结点向 对应的结点连容量为 、费用为 的边。源点连最左端,最右端连汇点,跑流量为 的最小费用流。
一条从源点到汇点的流对应一台机器的时间线。流过区间边表示该机器选择这个区间;区间边容量为 ,保证一个区间至多被一台机器选择;链边容量为 ,保证任意时刻至多 个区间同时进行。最小费用的相反数就是最大总权值。
费用为负,初次可使用 SPFA/Bellman–Ford,之后用势能 + Dijkstra 做连续最短路增广。
复杂度
离散化后有 个结点和边。进行 次增广,每次最短路为 ,总时间为 ,空间为 。