【BZOJ1061】【NOI2008】志愿者招募

一道费用流神题啊。。

用费用流应该是可以一眼秒的,然而建图是个大问题。。

去看了看BYVoid大神的题解,然后想到好像今年集训队论文一堆线性规划网络流肯定有讲这道题的。。果不其然找到了

这道题的建模是基于流量平衡的思想的。

举论文里的例子来说:

假设有三天,第\(i\)天需要\(a_i\)人

有三类志愿者:

第1天到第3天,费用为\(c_1\),招募\(b_1\)人
第2天到第3天,费用为\(c_2\),招募\(b_2\)人
第1天到第2天,费用为\(c_3\),招募\(b_3\)人

那么可以得到不等式组:

\(b_1+b_3\ge a_1\)
\(b_1+b_2+b_3\ge a_2\)
\(b_1+b_2\ge a_3\)

将不等式转化为等式就是

\(b_1+b_3-k_1=a_1\)
\(b_1+b_2+b_3-k_2=a_2\)
\(b_1+b_2-k_3=a_3\)

其中k代表的含义是该日多出的志愿者

首尾各添加一个0=0,然后相邻两式相减可以得到

\(b_1+b_3−a_1−k_1=0\)
\(b_2−a_2+a_1−k_2+k_1=0\)
\(−b_3−a_3+a_2−k_3+k_2=0\)
\(−b_1−b_2+a_3+k_3=0\)

那么可以发现,所有变量都只出现了两次,并且一次系数为正,一次为负。

a是常量,那么剩下的b和k就可以作为网络流的参数。

在网络流中,一个点要满足流量平衡,也就是流入=流出。对于这道题,我们可以将每个式子转化为一个点,每个变量看作一条边,那么正项表示流出,负项表示流入。

连边的方法为:

从每个含\(b_i\)式向含\(-b_i\)式连一条容量\(+\infty\),权值\(c_i\)的边

从每个含\(k_i\)式向含\(-k_i\)式连一条容量\(+\infty\),权值\(0\)的边

从S向每个常数项为正的项连一条权值为常数项的边

从每个常数项为负的项向T连一条权值为常数项的绝对值的边

然后跑费用流即可。

说点什么

  Subscribe  
提醒