「网络流24题」运输问题-题解

题目传送门: 「Luogu P4015」运输问题

题目大意

$m$个仓库,$n$个商店,每个仓库有$a_i$个货物,每个商店需要$b_i$个货物
需要从仓库运输货物到商店中,且第$i$个仓库运输到第$j$个商店费用为$c_{i,j}$

求最小费用和最大费用

题解

P4015 分配问题一样
将所有仓库和所有商店各分为一个点集

  1. 从 源点 向 每个仓库 建一条 容量为货物个数$a_i$,费用为$0$ 的边(有$a_i$个货物需要运出,且对答案无贡献)
  2. 从 每个商店 向 汇点 建一条 容量为货物个数$b_i$,费用为$0$ 的边(需要$b_i$个货物,且对答案无贡献)
  3. 从 每个仓库 向 每个商店 建一条 容量为$inf$,费用为对应费用 的边(每个仓库可以运出的最多货物不限制,且对答案工作为对应费用)

求出最小费用最大流和最大费用最大流即可

由于费用流的大前提是流量最大,所以一定满足题目中要求的供需平衡即$\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_j$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 费用流模板省略,在P4015题解那里有
// 代码里为了方便把mn调换了
int input1[110], input2[110], input3[110][110];

int main() {
n = read(); m = read();
s = 0; t = n + m + 1;

for (int i = 1; i <= n; ++i) {
int c = read(); input1[i] = c;
add(s, i, c, 0);
}
for (int i = 1; i <= m; ++i) {
int c = read(); input2[i] = c;
add(i + n, t, c, 0);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int c = read(); input3[i][j] = c;
add(i, j + n, inf, c);
}
}
ansflow = MinCostMaxFlow(anscost);
printf("%lld\n", anscost);

edges.clear();
for (int i = 0; i < maxn; ++i) G[i].clear();
for (int i = 1; i <= n; ++i) add(s, i, input1[i], 0);
for (int i = 1; i <= m; ++i) add(i + n, t, input2[i], 0);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
add(i, j + n, inf, input3[i][j]);
}
}
ansflow = MaxCostMaxFlow(anscost);
printf("%lld\n", anscost);

return 0;
}

「网络流24题」运输问题-题解

https://blog.tonycrane.cc/p/152673e9.html

作者

TonyCrane

发布于

2020-04-23

更新于

2020-05-05

许可协议

评论