BZOJ 1061 [Noi2008] 志愿者招募

发布于 2017-05-18  337 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1061

题意:n 天的活动,每天 至少 需要一定的志愿者,有 m 种志愿者,他们的人数不限,对于第 i 种志愿者,工作时间为 [si , ti],雇佣一名的费用是 ci,求最小费用


目前已知比较常见的解法有三种:

  1. 单纯形
  2. 不等式建模
  3. 奇技淫巧

由于博主弱,不会 1

对于方法 2, 这里 已经解释的足够清楚了,方法很妙,然而我并不会,所以 YY 了一个奇技淫巧,貌似已经有人写过了 orz

对于朴素的限制最大流量的问题,我们可以直接费用流解决,但是本题限制了最小流量,我们采用如下建边策略:

对于第 i 天和第 i+1 天间,建立流量为 inf,费用为 0 的边,使得最大流为 inf,对于第 i 天的限制,我们将第 i 天和第 i+1 天间的边流量减少 a[i],这样做后最大流就不是 inf 了,怎么办呢,我们通过雇佣志愿者来补上这些流量,使得最大流始终为 inf,具体做法就是对于工作时间在 [l,r],费用 c[i] 的志愿者,在第 l 天和第 r+1 天间连一条流量为 inf,费用为 c[i] 的边,至此,最大流一定为 inf 了

这样我们就解决了限制最小流的问题,为了保证最大流是 inf,我们一定会跑一些志愿者边,同时费用流的策略就可以满足费用最小了... 说的有点傻,感性理解吧...

 


一个非常弱的准退役OIER