BZOJ1061 - [Noi2008]志愿者招募

BZOJ1061 - Click Here

  

Description

  申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。经过估算,这个项目需要N 天才能完成,其中第i 天至少需要Ai个人。 布布通过了解得知,一共有M类志愿者可以招募。其中第i类可以从第Si天工作到第Ti天,招募费用是每人Ci元。新官上任三把火,为了出色地完成自己的工作,布布希望用尽量少的费用招募足够的志愿者,但这并不是他的特长!于是布布找到了你,希望你帮他设计一种最优的招募方案。

  

Input

  第一行包含两个整数N, M,表示完成项目的天数和可以招募的志愿者的种类。

  接下来的一行中包含N 个非负整数,表示每天至少需要的志愿者人数。

  接下来的M 行中每行包含三个整数Si, Ti, Ci,含义如上文所述。为了方便起见,我们可以认为每类志愿者的数量都是无限多的。

  

Output

  仅包含一个整数,表示你所设计的最优方案的总费用。

  

Solutions

  一年前曾经用单纯形水过该题,但是现在已经忘光了233。所以此处就先讲讲费用流做法,有时间再来填单纯形的坑。

  

  该题可以转换成线性规划问题。

  设第$i$志愿者的招募人数为$x_i$。那么对于某一天$p$,需要满足$a_p \leq \sum_{S_i \leq p \leq T_i} x_i$,且要求最小化$\sum x_iC_i$

  考虑将不等式化为等式。令$a_p + k_p = \sum_{S_i \leq p \leq T_i} x_i$,其中$0 \leq k_p$

  在等式首末位置均加上$0 = 0$,并对其差分。那么每个等式变成

  

  注意到差分后,每个变量只出现两次,且两次出现的符号相反。因此可以将每个变量看成流入量或流出量,等式代表流量守恒。至于常数项,则可以建立源点、汇点对其限制。

  又因为$x_i$加$1$需要产生$C_i$的费用,因此按照等式建立费用流模型,最后跑最小费用最大流即可。

  

CODE

CODE(单纯形) - Click Here

CODE(费用流) - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang