

$19.$负载平衡问题

题目

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

题解

考虑费用流。 首先可以确定每个仓库货物量最后应该是多少。 肯定是平均数。 然后考虑建模。 建立 $S$, $T$,然后将仓库按照货量与平均值的关系，大于平均值的放右边，小于平均值的放左边。 由 $S$ 向左边的集合连边，流量 $a[i]-sum$, 费用为零，表示最多可从 $S$ 点获得这么多流量，或者说实际上是可以向外最多移动这么多自己原有的货物。 由右边的集合向 $T$ 连边，流量为 $sum-a[i]$，费用为零，意义和上面的差不多。 考虑左右边集合之间的连边，由题目意思，只能相邻之间的仓库之间运输，所以相邻的点之间连边，流量为 $INF$，费用为1。 然后跑费用流输出最小费用就行。