「网络流24题」负载平衡问题-题解

题目传送门: 「Luogu P4016」负载平衡问题

题目大意

有$n$个环形的仓库,每个仓库存储一定数量的货物
货物可以在相邻仓库之间搬运,最终达到每个仓货物数量一样的效果

求最少搬运次数

题解

看题解说可以用数学方法推导,但是在24题里还是选择用费用流水过

先求出平均数,即目标
然后将每个仓库的货物数减去平均数,得出需要移动的数量

  1. 如果大于$0$,则从 源点 向 该仓库 建一条 容量为差值,费用为$0$ 的边(需要转移出,对答案无贡献)
  2. 如果小于$0$,则从 该仓库 向 汇点 建一条 容量为差值绝对值,费用为$0$ 的边(吸收这些货物,对答案无贡献)
  3. 从 每个仓库 向 相邻两个仓库 建一条 容量为$inf$,费用为$1$ 的边(转移货物的数量无要求,对答案贡献为$1$)

注意建边3.需要考虑环形
求出最小费用最大流,最小费用即为结果

因为费用流大前提是满足最大流,而且此图中源点出发的与流入汇点的边的容量和相等,所以最大流情况下一定会全部流过,即达到仓库货物数量平衡

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 最小费用最大流模板省去了
int num[110], tot;

int main() {
n = read(); s = 0; t = n + 1;
for (int i = 1; i <= n; ++i) {
num[i] = read(); tot += num[i];
}
tot /= n;
for (int i = 1; i <= n; ++i) {
if (num[i] - tot > 0) add(s, i, num[i] - tot, 0);
if (num[i] - tot < 0) add(i, t, tot - num[i], 0);
if (i != 1) {
add(i, i - 1, inf, 1);
add(i - 1, i, inf, 1);
}
}
add(1, n, inf, 1);
add(n, 1, inf, 1);
ansflow = MinCostMaxFlow(anscost);
printf("%lld\n", anscost);
return 0;
}

「网络流24题」负载平衡问题-题解

https://blog.tonycrane.cc/p/b8624866.html

作者

TonyCrane

发布于

2020-04-23

更新于

2020-05-05

许可协议

评论