【网络流24题】负载平衡问题

2014年3月11日1,8630

题目描述 Description

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

输入描述 Input Description

第1 行中有1 个正整数n(n<=100),表示有n
个仓库。第2 行中有n个正整数,表示n个仓库的库存量。

输出描述 Output Description

将计算出的最少搬运量输出

样例输入 Sample Input

5
17 9 14 16 4

样例输出 Sample Output

11

题解

【问题分析】

转化为供求平衡问题,用最小费用最大流解决。

【建模方法】

首先求出所有仓库存货量平均值,设第i个仓库的盈余量为A[i],A[i] = 第i个仓库原有存货量 – 平均存货量。建立二分图,把每个仓库抽象为两个节点Xi和Yi。增设附加源S汇T。

1、如果A[i]>0,从S向Xi连一条容量为A[i],费用为0的有向边。
2、如果A[i]<0,从Yi向T连一条容量为-A[i],费用为0的有向边。
3、每个Xi向两个相邻顶点j,从Xi到Xj连接一条容量为无穷大,费用为1的有向边,从Xi到Yj连接一条容量为无穷大,费用为1的有向边。

求最小费用最大流,最小费用流值就是最少搬运量。

【建模分析】

计算出每个仓库的盈余后,可以把问题转化为供求问题。建立供求网络,把二分图X集合中所有节点看做供应节点,Y集合所有节点看做需求节点,在能一次搬运满足供需的Xi和Yj之间连接一条费用为1的有向边,表示搬运一个单位货物费用为1。另外还要在Xi与相邻的Xj之间连接边,表示货物可以暂时搬运过去,不立即满足需求,费用也为1。最大流满足了所有的盈余和亏损供求平衡,最小费用就是最少搬运量。