CodeChef上一道有趣的网络流题目

这是一道2016年二月CodeChef上的一道题目,叫做Call Center Schedule

题目大意是这样的:

一个电话公司有 P 个员工,一个星期有 D 天,每天需要工作 H 个小时。每个员工在每个小时只能做参加会议和与客户通话两件事情中的一件,或者不做。

现在要为安排一个和客户通话的时间表,要求满足

  • 每个人每天最多花费 N 个小时在参加会议和通话上
  • 第 i 个人每周最多花费 Li 个小时和客户通话
  • 每个人每天在 LTbegin 到 LTend 的时间内至少要有 1 小时没有被安排任务
  • 对于第 i 天第 j 个小时,恰好有 Ri, j 个人可以和客户通话

另外,开会的时间表已经安排完成,如果 Fk, i, j 是 0 则表示第 k 个人在第 i 天的第 j 个小时开会,如果是 1 则表示他可以被安排去和客户通话。

时限是 2s,最多 5 组数据,并且 1 \leq N \leq H \leq 70, 1 \leq D, P \leq 70, 1 \leq L_i \leq ND, 0 \leq R_{i, j} \leq 15, F_{k, i, j} \in \{0, 1\}, 1 \leq LT_{begin} \leq LT_{end} \leq N

(more…)

Read More