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