【费用流】luogu_P3980 [NOI2008] 志愿者招募

题意

项目需\(n\)天才能完成,其中第\(i\)天至少需要\(a_i\)个人。
一共有\(m\)类志愿者可以招募。其中第\(i\)类可以从第\(s_i\)天工作到第\(t_i\)天,招募费用是每人\(c_i\)元。
设计一种最优的招募方案使得用尽量少的费用招募足够的志愿者。
\(1\leq n\leq 1000,1\leq m\leq 10000\),题目中其他所涉及的数据均不超过\(2^{31}-1\)。

思路

由于天数够多,状态极大,可以考虑网络流。
\(i\)点向\(i+1\)点连一条\((0,INF-a_i)\)//(费用,容量)的边,代表第\(i\)天的要求(为了走出最大流,即至少要有\(a_i\)个人走的是加权的、覆盖了第i天的边)。
对于第\(i\)类志愿者,\(s_i\)向\(t_i+1\)连一条\((c_i,INF)\),代表这个人可以覆盖\(s_i~t_i\)天。
最后求一遍最小费用最大流,最小费用即为答案。由于最大流为\(INF\),所以第i天无法走的\(a_i\)个流量会从加权边走过。

当然还有一种可以用线性规划做的建图方法,(待填坑)。

代码

上一篇:luogu P4422 题解


下一篇:[BUUCTF][RoarCTF 2019]Easy Java