负载平衡问题
Time Limit: 1000ms, Memory Limits: 256MB
Total Submission: 1.4k, Accepted Submission: 774
题目描述
G 公司有$n$个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使$n$个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。
输入输出格式
输入格式
第 1 行中有 1 个正整数 $n$,表示有 $n$ 个仓库。
第 2 行中有 $n$ 个正整数,表示 $n$ 个仓库的库存量。
输出格式
输出最少搬运量。
输入输出样例
输入样例
5
17 9 14 16 4
输出样例
11
说明
$$ 1 \leq n \leq 100$$
Solution
显然,最终的仓库库存为所有仓库的初始库存的平均值。
先建立超级源点与超级汇点。对于每一个初始库存$a_i$大于平均值$ave$的仓库,与超级源连一条边,流量为$a_i - ave$,费用为0。对于每个初始库存$a_i$小于平均值$ave$的仓库,与超级汇连一条边,流量为$ave - a_i$,费用为0。在所有相邻的两仓库间连一条边,流量为infi, 费用为1。然后跑一遍费用流,结果即为$ans$。
Code
1 |
|