「POI2011 R3」程序设计竞赛 题解

题意

$n$ 个队员，$m$ 道题

解题需 $r$ 分钟，比赛 $t$ 分钟

已知队员能解哪些题

目标：①最多解题数 ②最小罚时（罚时=完成时刻和）

解法：费用流 建图 源点→队员：第 $k$ 条边（$1≤k≤\lfloor t/r\rfloor$）

容量 1，费用 $M-k×r$（$M$ 取大数如 $10^9$）

表示队员解的第 $k$ 题，罚时 $k×r$

队员→题目：队员 $i$ 能解题 $j$

容量 1，费用 0

题目→汇点：

容量 1，费用 0

原理 费用 $=M-$罚时

$M$ 很大 → 优先解更多题（费用大），再减少罚时

跑最小费用最大流 得到流量 $F$（解题数）

总费用 $C$

总罚时 $=F×M - C$

提取方案 队员 $i$ 解的第 $k$ 题 → 开始时间 $=(k-1)×r$

复杂度

$O(\text{费用流})$，$n,m≤500$ 可过