题目描述：

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的代码秒杀网络流。

设仓库的编号分别为u₁,u₂,u₃..u_n ,仓库u_i给了仓库u_i+1 x_i 件货物（可以为负数,即u_i+1给u_i货物）, x_n表示u_n给u_1 。

各个仓库的初始货物数量分别为a₁，a₂,a₃...a_n

那么有

a₁+x_n-x₁=ave

a₂+x₁-x₂=ave

a₃+x₂-x₃=ave

......

a_n+x_n-1-x_n=ave

可以发现当x_n确定的时候，所有的x_i便确定了。

变换一下式子，那么有

x₁=x_n-(ave-a₁)

x₂=x_n-[(ave-a₁)+(ave-a₂)]

x₃=x_n-[(ave-a₁)+(ave-a₂)+(ave-a₃)]

......

x_n=x_n-0

现在的目标是最小化|x₁|+|x₂|+|x₃|......+|x_n|

也就是最小化数轴上点x_n到(ave-a₁)，[(ave-a₁)+(ave-a₂)]，[(ave-a₁)+(ave-a₂)+(ave-a₃)]...0 这些点的距离之和。

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

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

问题是否就解决了呢？

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

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

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

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

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

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