【NOI2008】志愿者招募

转自\(dugudashen\)的\(cnblogs\)。比起其他比较神奇的建图方法，还是这种简单粗暴的常规但是不好想的想法更让我拜服，拿过来学习一个。

无源汇上下界最小费用可行流。

每天作为一个点。

每一天向下一天连一条上界为正无穷下界为该天所需人数费用为\(0\)的边。

对于每个志愿者，从他结束工作的后一天向开始工作的第一天连一条上界为正无穷下界为\(0\)费用为招募费的边。

在这个无源汇网络中，招募一个志愿者即产生一个\(Ti+1—>Si—>Si+1—>Si+2—>……—>Ti—>Ti+1\)的圈，使\(Si\)到\(Ti\)天的流量加\(1\)。

原图跑无源汇上下界最小费用可行流就行了。

类比\(poj3680\)，对于一个条件覆盖连续点问题，通常用将点依次相连再加边的方式，两题区别在于有上界正向连边最大流，有下界反向连边可行流。

【NOI2008】志愿者招募

原文：https://www.cnblogs.com/maomao9173/p/10434512.html