「网络流24题」数字梯形问题-题解

题目传送门: 「Luogu P4013」数字梯形问题

题目大意

梯形的第一行有$m$个数字
从梯形的顶部的$m$个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

有三种规则:

  1. 从梯形的顶至底的$m$条路径互不相交
  2. 从梯形的顶至底的$m$条路径仅在数字结点处相交
  3. 从梯形的顶至底的$m$条路径允许在数字结点相交或边相交

求每种规则下经过数字的最大总和

题解

很明显是 最大费用最大流

规则1.

路径不相交,即没有公共点,也就是每个点只能经过一次
将每个点拆成入点和出点,就可以通过控制出入点之间的容量控制经过次数

  1. 从 源点 向 第一行的$m$个点的入点 接一条 容量为$1$,费用为$0$ 的边
  2. 从 最后一行每个点的出点 接一条 容量为$1$,费用为$0$ 的边
  3. 从 每个点的入点 向 每个点的出点 接一条 容量为$1$,费用为该点数字 的边(对答案贡献为该点数字)
  4. 从 每个点的出点 向 左下右下两个点的入点 接一条 容量为$1$,费用为$0$ 的边

规则2.

每条路径仅在数字节点相交,也就是不能有重边
无需拆点控制每个点经过的次数,只需给每条向左下右下的边的容量设为$1$,即只能经过一次

  1. 从 源点 向 第一行的$m$个点 接一条 容量为$1$,费用为$0$ 的边
  2. 从 最后一行每个点 接一条 容量为$inf$,费用为该点数字 的边(每个点可以使用多次)
  3. 从 每个点的 向 左下右下两个点 接一条 容量为$1$,费用为该点数字 的边

规则3.

边也可以重合,也就相当于没有规则,可以随意向左下右下走
只需将规则2.中建边3.的容量改成$inf$即可

对于每种情况,求出最大费用最大流,最大费用即为答案
注意求解规则2.3.之前要清空建的图

代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 最大费用最大流模板部分省去了
int in[45][45];
int point[45][45], cnt;

int main() {
m = read(); n = read();
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m + i - 1; ++j) {
in[i][j] = read();
point[i][j] = ++cnt;
}
}

// Question 1
s = 0; t = cnt * 2 + 1;
for (int i = 1; i <= m; ++i) add(s, point[1][i], 1, 0);
for (int i = 1; i <= n + m - 1; ++i) add(point[n][i] + cnt, t, 1, 0);
for (int i = 1; i <= n; ++i) {
if (i < n) for (int j = 1; j <= m + i - 1; ++j) {
add(point[i][j] + cnt, point[i + 1][j], 1, 0);
add(point[i][j] + cnt, point[i + 1][j + 1], 1, 0);
}
for (int j = 1; j <= m + i - 1; ++j)
add(point[i][j], point[i][j] + cnt, 1, in[i][j]);
}
ansflow = MaxCostMaxFlow(anscost);
printf("%lld\n", anscost);

// Question 2
edges.clear();
for (int i = 0; i < maxn; ++i) G[i].clear();
s = 0; t = cnt + 1;
for (int i = 1; i <= m; ++i) add(s, point[1][i], 1, 0);
for (int i = 1; i <= n + m - 1; ++i) add(point[n][i], t, inf, in[n][i]);
for (int i = 1; i < n; ++i) for (int j = 1; j <= m + i - 1; ++j) {
add(point[i][j], point[i + 1][j], 1, in[i][j]);
add(point[i][j], point[i + 1][j + 1], 1, in[i][j]);
}
ansflow = MaxCostMaxFlow(anscost);
printf("%lld\n", anscost);

// Question 3
edges.clear();
for (int i = 0; i < maxn; ++i) G[i].clear();
s = 0; t = cnt + 1;
for (int i = 1; i <= m; ++i) add(s, point[1][i], 1, 0);
for (int i = 1; i <= n + m - 1; ++i) add(point[n][i], t, inf, in[n][i]);
for (int i = 1; i < n; ++i) for (int j = 1; j <= m + i - 1; ++j) {
add(point[i][j], point[i + 1][j], inf, in[i][j]);
add(point[i][j], point[i + 1][j + 1], inf, in[i][j]);
}
ansflow = MaxCostMaxFlow(anscost);
printf("%lld\n", anscost);

return 0;
}

「网络流24题」数字梯形问题-题解

https://blog.tonycrane.cc/p/86b4c1f9.html

作者

TonyCrane

发布于

2020-04-23

更新于

2020-05-05

许可协议