AC. 梦想

frank_c1

[BZOJ 1061] 志愿者招募

发布于2016年03月06日 | 2条评论 | 1,909阅读 | 单纯形

题目描述

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

输入格式

第一行包含两个整数N, M,表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负整数,表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci,含义如上文所述。为了方便起见,我们可以认为每类志愿者的数量都是无限多的。

输出格式

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

题目解析

感觉比前面那题更直接……

设招募第i类志愿者x_i人,S_{ij}表示第i天第j类志愿者是否工作,1表示工作,0表示不工作。可写出线性规划:

\begin{equation} \min {w =\sum_{i=1}^{m} {C_{i} x_{i}}} \\ \left\{ \begin{aligned} \sum_{j=1}^{m} {S_{ij} x_{j}} & \ge A_{i} (1 \le i \le n) \\ x_{i} & \ge 0 (1 \le i \le m) \\ \end{aligned} \right. \nonumber \end{equation}

根据对偶原理转化为标准形式:

\begin{equation} \max {z =\sum_{i=1}^{n} {A_{i} y_{i}}} \\ \left\{ \begin{aligned} \sum_{j=S_{i}}^{T_{i}} {y_{j}} & \le C_{i} (1 \le i \le m) \\ y_{i} & \ge 0 (1 \le i \le n) \\ \end{aligned} \right. \nonumber \end{equation}

为了表述地更清晰,给出样例数据的系数矩阵。

2016030102

又可以开心地上单纯形啦。本题也是幺模矩阵,无需浮点数。另外,本题的做法稍加改动可以解决[BZOJ 3265] 志愿者招募加强版,不再赘述。

  • LZ,n和m打反了,感觉去举报数据水啊!

    • 居然都是n=m的点……现在已改正