首页 > 代码库 > 网络流24题之负载平衡问题

网络流24题之负载平衡问题

题目描述:

G 公司有n 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使n 个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。对于给定的n 个环形排列的仓库的库存量,编程计算使n 个仓库的库存数量相同的最少 搬运量。

 

模型分析:

1.首先弄清楚题目要求什么,最终流量应该是确定的,所以应该是在最大流的前提下使得费用最小,也就是最小费用流问题。

2.题目有2个限制条件,一个是最终每个仓库的库存量都必须是ave(原库存的平均数),一个是只能相邻仓库之间才能运货。

3.对于第一个条件,可以想象有1个超级大的仓库T,最终所有仓库的货物都要运到它那里,那么只要让所有仓库到T的弧的容量为ave,在最大流的前提下,最终这些弧一定是满载的,也就是说最终所有的仓库的货物都是ave。 另外每个仓库一开始也有一些货物,同样的道理只要增加一个大仓库S,让S到其他仓库的弧的容量为这些仓库的初始货物量,,在最大流的前提下,最终这些弧一定是满载的,也就是说所有仓库一开始的货物确定了。当然这些弧都是不要费用的。

4.对于第二个条件,自然想到可以让相邻的仓库之间连容量为inf,费用为1的边,那么求最小费用流就是答案了。

 

构图方法:

1.增加源点S和汇点T。

2.从S到所有仓库连一条容量为仓库初始货物数量,费用为0的边。

3.从所有仓库到T连一条容量为ave,费用为0的边。

4.相邻的仓库之间连容量为inf,费用为1的边。

 

总结:

熟悉了最小费用最大流的连续最短路做法,第一次写还真是错误百出,调试了好久。

 


 

其实这道题我一开始的做法是数学做法,600B的代码秒杀网络流。

设仓库的编号分别为u1,u2,u3..un ,仓库ui给了仓库ui+1 xi 件货物(可以为负数,即ui+1给ui货物), xn表示un给u1 。

各个仓库的初始货物数量分别为a1,a2,a3...an

那么有

a1+xn-x1=ave

a2+x1-x2=ave

a3+x2-x3=ave

......

an+xn-1-xn=ave

可以发现当xn确定的时候,所有的xi便确定了。

变换一下式子,那么有

x1=xn-(ave-a1)

x2=xn-[(ave-a1)+(ave-a2)]

x3=xn-[(ave-a1)+(ave-a2)+(ave-a3)]

......

xn=xn-0

现在的目标是最小化|x1|+|x2|+|x3|......+|xn|

也就是最小化数轴上点xn到(ave-a1),[(ave-a1)+(ave-a2)],[(ave-a1)+(ave-a2)+(ave-a3)]...0 这些点的距离之和

问题转化为给定数轴上n点,求数轴上一点P使得这n个点到P的距离之和最小,这就涉及中位数的一些知识了,只要按坐标排序,取第(n+1)/2个点所在的位置就可以了。具体的证明也很简单,可以查阅相关资料。

 

按照这个方法写的程序,在OJ上测评AC了。

问题是否就解决了呢?

以前做某一年NOIP一道叫均分纸牌的题目,方法也有些类似,当时我就一直在想,对于合法的序列x1,x2...xn,是否一定存在方案使得移动的总步数为它们的绝对值之和呢? 比如一个仓库本来只有5件货物,但是它要给右边的仓库10件货物,那么必须要它左边的仓库给它5件货,那么要是它左边的仓库货也不够呢?一直推下去,会不会存在一个状态,使得没有一个仓库可以满足它的xi呢?

这个问题困扰了我很久,前几天火来直接拿了一节晚自习”冥想“,结果还真想出来了。

首先对于xi,如果它为正,那么连一条弧<i,i+1>,容量为xi。如果是负,那么连一条弧<i,i-1>,容量为-xi

对于上面提到的情况,我们没有必要一次性满足xi,也就是现在有多少货,如果要分给旁边的,就先分给它。

对于当前货物数量大于ave的仓库,必然有没有满载的弧连向边上的点,否则最后它的货物怎么会ave呢。那么每次至少可以让一条弧的流量+1,直到最后所有弧都满载,那么就不可能出现卡死的局面了。 可能有人会说如果当前没有货物数量大于ave的仓库,那就无法移动了。其实由于总的货物数量是ave*n,那么只能是所有仓库的货物都是ave,那么这个时候已经完成任务了。

 

 

 

 

网络流24题之负载平衡问题