4597 - NOIP CSP 2021 提高: 第四题交通规划（traffic）

通过次数

提交次数

旧版界面

时间限制 : 1 秒

内存限制 : 512 MB

给定一个平面上 n 条水平直线和 m 条垂直直线，它们相交形成 n 行 m 列的网格，从上到下第 r 条水平直线和从左到右第 c 条垂直直线之间的交点称为格点 (r, c)。网格中任意两个水平或垂直相邻的格点之间的线段称为一条边，每条边有一个非负整数边权。进行 T 次询问，每次询问形式如下：给出 k（T 次询问的 k 可能不同）个附加点，每个附加点位于一条从网格边缘向外出发的射线上。所有从网格边缘向外出发的射线按左上-右上-右下-左下-左上的顺序依次编号为 1 到 2n + 2m，如下图：图 2: 射线的编号对于每次询问，不同附加点所在的射线互不相同。每个附加点和最近的格点之间的线段也称为一条边，也有非负整数边权（注意，在角上的格点有可能和两个附加点同时相连）。给定每个附加点的颜色（黑色或者白色），请你将网格内每个格点的颜色染成黑白二者之一，并使得所有两端颜色不同的边的边权和最小。请输出这个最小的边权和。

输入

第一行 3 个正整数 n, m, T 分别表示水平、垂直直线的数量，以及询问次数。接下来 n − 1 行，每行 m 个非负整数。其中第 i 行的第 j 个非负整数 x1i,j 表示(i, j) 和 (i + 1, j) 间的边权。接下来 n 行，每行 m − 1 个非负整数。其中第 i 行的第 j 个非负整数 x2i,j 表示(i, j) 和 (i, j + 1) 间的边权。接下来依次输入 T 组询问。第 i 组询问开头为一行一个正整数 ki 表示这次询问附加点的总数。接下来 ki 行每行三个非负整数。其中第 j 行依次为 x3ij , pij , tij 表示第 i个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色（0 为白色，1 为黑色）。保证同一组询问内 pi,j 互不相同。每行的多个整数由空格分隔。

输出

输出 T 行，第 i 行输出一个非负整数，表示第 i 次询问染色之后两端颜色不同的边权和的最小值。

样例

输入

输出

输入

5 5 5
17028 678493 790877 16274 4341
53383 504487 629344 922030 634468
13192 2596 992150 561737 9167
2191 50115 854392 272504 148247
3826 16761 15532 1174
17939 2393 505972 217167
939238 668146 306243 631745
440326 319998 649845 15540
10494 756726 237185 867714
17
978310 3 1
949903 11 0
994542 9 0
994842 20 1
936919 6 0
971685 10 1
963940 1 1
968594 5 1
953297 14 1
949338 18 0
920639 13 0
946444 2 1
954164 12 1
999155 19 1
960560 17 1
998252 16 0
950264 4 0
15
979754 3 0
914919 19 1
938570 6 0
969294 8 0
902653 16 1
987811 1 0
926801 13 1
973947 12 0
976949 14 0
951338 15 0
961809 17 1
940796 20 0
960186 18 1
982315 5 1
907884 7 0
12
987622 17 0
962444 13 1
919937 11 1
936189 9 1
957129 18 1
980858 14 0
917858 19 0
967204 1 0
923028 5 1
973847 15 0
905378 10 0
900364 4 1
4
914598 1 1
925997 20 0
953048 14 0
981502 11 0
2
927011 12 0
990228 19 1

输出

输入

18 18 25
60 0 74 45 94 78 74 56 0 0 73 39 77 27 0 31 60 0
0 42 25 0 25 0 0 0 43 0 93 0 66 0 0 87 76 89
89 68 11 0 98 17 56 45 51 0 28 77 53 25 64 0 0 0
81 72 23 0 8 0 0 0 50 68 74 83 63 8 78 0 0 99
0 78 0 20 72 16 0 0 7 96 0 89 5 0 15 11 52 30
58 0 91 0 62 0 56 18 0 47 65 23 0 64 40 36 96 28
0 0 0 66 0 86 0 21 0 0 26 0 65 0 28 0 72 92
97 95 89 0 96 0 50 30 63 31 0 11 93 0 77 0 41 94
83 0 0 8 54 50 0 0 33 73 84 35 93 57 0 93 0 0
38 0 10 41 0 0 52 66 0 0 69 0 0 73 28 0 0 41
30 11 0 87 0 71 53 0 73 0 0 69 67 51 21 94 0 0
60 10 76 23 99 9 69 81 34 4 67 10 0 96 0 54 49 44
49 89 0 15 72 92 0 61 62 65 0 14 0 0 12 0 90 79
0 50 50 42 0 2 0 98 5 44 69 5 0 19 24 22 64 64
0 66 41 60 54 22 34 39 0 0 59 93 97 43 54 0 52 0
95 0 0 42 10 0 61 44 73 0 0 67 0 32 0 26 80 80
0 30 38 96 91 34 48 47 0 0 0 0 0 70 0 12 35 0
75 0 0 95 0 0 0 82 0 27 98 46 0 0 22 0 24
35 40 38 0 28 0 24 0 86 49 0 76 0 0 81 29 0
37 0 22 0 0 68 36 0 14 0 0 0 52 28 0 0 47
0 0 14 51 37 24 37 0 82 0 29 77 80 95 25 23 0
95 0 0 25 64 0 0 29 0 29 0 31 0 22 1 91 0
63 34 0 0 79 0 0 83 33 17 69 0 56 0 73 64 0
0 36 40 0 51 94 62 11 40 29 71 37 0 0 8 9 82
21 0 62 25 0 0 49 65 2 0 0 0 72 79 94 65 0
0 0 62 0 28 0 39 0 0 2 0 36 0 29 13 89 0
4 0 43 94 27 0 79 0 20 36 0 2 19 11 2 0 97
30 0 0 94 36 41 0 58 0 45 46 0 0 29 35 7 45
71 0 0 0 0 33 77 0 78 52 47 1 21 49 0 0 2
0 3 0 39 67 93 13 66 74 0 18 38 15 0 0 62 29
0 0 12 45 27 11 0 29 60 57 39 0 63 79 50 0 84
63 0 0 77 87 41 23 0 0 66 0 0 81 73 80 12 0
92 24 39 77 96 14 0 48 18 55 98 28 32 0 0 0 47
42 0 0 86 66 61 24 0 0 0 0 0 0 0 0 0 45
0 25 31 0 0 21 36 79 0 48 0 8 97 0 0 77 54
2
98 43 0
98 2 1
2
99 54 1
99 22 0
2
98 49 0
93 34 1
2
95 41 0
97 59 1
2
93 47 1
93 28 0
2
95 21 1
93 6 0
2
96 58 0
92 1 1
2
100 55 0
97 25 1
2
91 8 1
96 17 0
2
91 20 1
94 47 0
2
91 10 0
96 5 1
2
97 28 1
94 66 0
2
95 26 0
92 40 1
2
94 8 1
99 33 0
2
95 45 1
93 37 0
2
100 31 0
95 18 1
2
97 24 0
95 25 1
2
100 16 0
98 21 1
2
93 43 0
93 5 1
2
91 31 0
99 33 1
2
93 69 0
95 66 1
2
100 38 1
92 49 0
2
92 68 0
99 57 1
2
96 45 0
92 64 1
2
96 4 0
98 19 1

输出

提示

【样例 1 解释】最优方案：(1, 3),(1, 2),(2, 3) 为黑色；(1, 1),(2, 1),(2, 2) 为白色

4597 - NOIP CSP 2021 提高: 第四题 交通规划（traffic）

输入

输出

样例

输入

输出

输入

输出

输入

输出

提示

4597 - NOIP CSP 2021 提高: 第四题交通规划（traffic）