P1588 - 【NOI2008】志愿者招募
Description
申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。经过估算,这个项目需要N 天才能完成,其中第i 天至少需要Ai 个人。
布布通过了解得知,一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天,招募费用是每人Ci 元。新官上任三把火,为了出色地完成自己的工作,布布希望用尽量少的费用招募足够的志愿者,但这并不是他的特长!于是布布找到了你,希望你帮他设计一种最 优的招募方案。Input
第一行包含两个整数N, M,表示完成项目的天数和可以招募的志愿者的种类。
接下来的一行中包含N 个非负整数,表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci,含义如上文所述。为了方便起见,我们可以认为每类志愿者的数量都是无限多的。Output
包含一个整数,表示你所设计的最优方案的总费用。
Sample Input
3 3
2 3 4 1 2 2 2 3 5 3 3 2Sample Output
14
Hint
【样例说明】
招募3 名第一类志愿者和4 名第三类志愿者。 【数据规模和约定】 30%的数据中,1 ≤ N, M ≤ 10,1 ≤ Ai ≤ 10; 100%的数据中,1 ≤ N ≤ 1000,1 ≤ M ≤ 10000,题目中其他所涉及的数据均不超过2^31-1。Source
NOI,数学 ,网络流 ,线性规划
每个时间像下一个时间连一条容量为inf-这个时间需要的人,费用为0。 S向1连容量为INF,费用为0。 N向T连容量为INF,费用为0。 然后对于每个人,时间段为x到y,费用为z,从x到y+1连一条容量为inf,费用为z的边。
然后跑最小费用最大流。
证明:(其实是瞎掰,欢迎大佬指出错误)
因为时间段之间连了inf-x的边,就相当于这条边控制了x的流量不能从这里流过,所以只能从那条有费用的边流过去。 把每个减了x的边想像成一个坑,这个坑需要用志愿者来填满。最大流肯定能把这个坑填满,所以求出最小费用最大流就可以了。
1 #include2 #include