[BZOJ1061/Luogu3980][Noi2008]志愿者招募(网络流,单纯型)

发布于 2018-02-11  4 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1061/Luogu3980][Noi2008]志愿者招募(网络流,单纯型)

Description

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

Http

BZOJ
Luogu

Tag

网络流,单纯型

解决思路

又是一道网络流神题。先看一个例子
假设总共\(5\)天,有四类志愿者,分别是\(1-2,1-5,2-4,3-5\),设\(P[i]\)表示第\(i\)天需要的人数,\(P[i]'\)表示第\(i\)天实际的人数,\(X[i]\)表示第\(i\)类志愿者的人数,则有下列不等式组
\[P[1]'=X[1]+X[2]>=P[1] \\ P[2]'=X[1]+X[2]+X[3]>=P[2] \\ P[3]'=X[2]+X[3]+X[4]>=P[3] \\ P[4]'=X[2]+X[3]+X[4]>=P[4] \\ P[5]'=X[2]+X[4]>=P[5]\]
对每一个式子补充一个\(Y[i]\)把不等式变成等式
\[P[1]'=X[1]+X[2]-Y[1]=P[1] \\ P[2]'=X[1]+X[2]+X[3]-Y[2]=P[2] \\ P[3]'=X[2]+X[3]+X[4]-Y[3]=P[3] \\ P[4]'=X[2]+X[3]+X[4]-Y[4]=P[4] \\ P[5]'=X[2]+X[4]-Y[5]=P[5]\]
设有\(P[0]=P[6]=0\),相邻两式相减,得到
\[P[1]'-P[0]'=X[1]+X[2]-Y[1]=P[1] \\ P[2]'-P[1]'=X[3]-Y[2]+Y[1]=P[2]-P[1] \\ P[3]'-P[2]'=X[4]-Y[3]-X[1]+Y[2]=P[3]-P[2] \\ P[4]'-P[3]'=-Y[4]+Y[3]=P[4]-P[3] \\ P[5]'-P[4]'=-Y[5]-X[3]+Y[4]=P[5]-P[4] \\ P[6]'-P[5]'=-X[2]-X[4]+Y[5]=-P[5] \]
发现,每一个\(X[i]\)和每一个\(Y[i]\)都在这些式子中恰好出现了一次。并且这些式子的和为\(0\),这里有没有想到与网络流的流量平衡有一些关系?
把左边去掉,留下中间的和右边的,移项得到
\[P[1]-X[1]-X[2]+Y[1]=0 \\ P[2]-P[1]-X[3]+Y[2]-Y[1]=0 \\ P[3]-P[2]-X[4]+Y[3]+X[1]-Y[2]=0 \\ P[4]-P[3]+Y[4]-Y[3]=0 \\ P[5]-P[4]+Y[5]+X[3]-Y[4]=0 \\ P[6]-P[5]+X[2]+X[4]-Y[5]=0\]
这样,把每一个等式看作一个点,前面符号为\(+\)的为流入的流量,符号为\(-\)的为流出的流量,当出入平衡时,这个方程组就有解。而\(P[i]-P[i-1]\)的常数项就相当于与源汇点连的边,这个值为正则是从源点流出来的,否则则是流向汇点的。
观察到对于一类可以从第\(i\)天到第\(j\)天的志愿者,他对应的\(X[]\)在第\(i\)个等式中为负,在第\(j+1\)个等式中为正,那么就从\(i\)到\(j+1\)连一条容量为无穷大费用为志愿者费用的边。对于\(Y[i]\)则同理,只是此时是没有费用的。建完图后跑最小费用流即可。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1061/Luogu3980][Noi2008]志愿者招募(网络流,单纯型)


HNCJ OIer 一枚