无源汇上下界最小费用可行流.
每天作为一个点.
每一天向下一天连一条上界为正无穷下界为该天所需人数费用为 \(0\) 的边.
对于每个志愿者, 从他结束工作的后一天向开始工作的第一天连一条上界为正无穷下界为 \(0\) 费用为招募费的边.
在这个无源汇网络中, 招募一个志愿者即产生一个 \(Ti+1->Si->Si+1->Si+2->......->Ti->Ti+1\) 的圈, 使 \(Si\) 到 \(Ti\) 天的流量加 \(1\).
原图跑无源汇上下界最小费用可行流就行了.
类比 \(poj3680\), 对于一个条件覆盖连续点问题, 通常用将点依次相连再加边的方式, 两题区别在于有上界正向连边最大流, 有下界反向连边可行流.
来源: http://www.bubuko.com/infodetail-2967874.html