夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色
网络流 24 题 – 负载平衡问题

题面

题目传送

题目描述

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

输入格式

第 $1$ 行中有 $1$个正整数 $n$,表示有 $n$ 个仓库。

第 $2$ 行中有 $n$ 个正整数,表示 $n$ 个仓库的库存量。

输出格式

输出最少搬运量。

思路

设平均值为 $\bar a$,$a[i]-\bar a$ 为 $b[i]$。

则对于结点 $i$,如果 $b[i]>0$ 则代表这个结点有多余的货物可以分给他人,从 $S$ 到 $i$ 连一条流量为 $b[i]$ ,费用为 $0$ 的边;

如果 $b[i]<0$ 则代表这个结点需要别人给的货物,从 $i$ 到 $T$ 连一条流量为 $-b[i]$ ($\bar a – a[i]$) ,费用为 $0$ 的边。

再从每个结点 $i$ 向环上相邻的点连流量为 $+ \infty$ ,费用为 $1$ 的边。

然后跑最小费用最大流。

因为 $\sum_{a\lbrack i\rbrack-\overline a>0}^{}a\lbrack i\rbrack-\overline a=\sum_{a\lbrack i\rbrack-\overline a<0}^{}\overline a-a\lbrack i\rbrack$ ,所以最终所有 $(i,T)$ 的边都会被填满,此时的费用即为最小。

代码

暂无评论

发送评论 编辑评论


				
上一篇
下一篇