s02272. CSP-S 2021 复赛 T4 交通规划

题目描述

时间限制：3s　内存限制：512MB　来源：洛谷 P7916

题目描述

给定一个平面上 $n$ 条水平直线和 $m$ 条垂直直线，它们相交形成 $n$ 行 $m$ 列的网格，从上到下第 $r$ 条水平直线和从左到右第 $c$ 条垂直直线之间的交点称为格点 $(r, c)$ 。网格中任意两个水平或垂直相邻的格点之间的线段称为一条边，每条边有一个非负整数边权。

进行 $T$ 次询问，每次询问形式如下：

给出 $k$ （ $T$ 次询问的 $k$ 可能不同）个附加点，每个附加点位于一条从网格边缘向外出发的射线上。所有从网格边缘向外出发的射线按左上-右上-右下-左下-左上的顺序依次编号为 $1$ 到 $2 n + 2 m$ ，如下图：

对于每次询问，不同附加点所在的射线互不相同。每个附加点和最近的格点之间的线段也称为一条边，也有非负整数边权（注意，在角上的格点有可能和两个附加点同时相连）。

给定每个附加点的颜色（黑色或者白色），请你将网格内每个格点的颜色染成黑白二者之一，并使得所有两端颜色不同的边的边权和最小。请输出这个最小的边权和。

输入格式

第一行，三个正整数 $n, m, T$ ，分别表示水平、垂直直线的数量，以及询问次数。

接下来 $n - 1$ 行，每行 $m$ 个非负整数。其中第 $i$ 行的第 $j$ 个非负整数 $x 1_{i, j}$ 表示 $(i, j)$ 和 $(i + 1, j)$ 间的边权。

接下来 $n$ 行，每行 $m - 1$ 个非负整数。其中第 $i$ 行的第 $j$ 个非负整数 $x 2_{i, j}$ 表示 $(i, j)$ 和 $(i, j + 1)$ 间的边权。

接下来依次输入 $T$ 组询问。第 $i$ 组询问开头为一行一个正整数 $k_{i}$ 表示这次询问附加点的总数。接下来 $k_{i}$ 行每行三个非负整数。其中第 $j$ 行依次为 $x 3_{i, j}, p_{i, j}, t_{i, j}$ 表示第 $j$ 个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色（ $0$ 为白色， $1$ 为黑色）。保证同一组询问内 $p_{i, j}$ 互不相同。

每行的多个整数由空格分隔。

输出格式

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

样例

输入

5 5 6
59 36 0 57 1
1 0 0 0 2
30 30 52 9 0
39 82 11 61 1
0 75 0 40
2 0 0 37
81 18 0 29
1 33 86 2
2 67 48 22
16
98 1 0
92 10 1
95 12 0
96 3 0
91 15 0
98 11 1
96 6 0
99 16 0
94 2 0
99 5 0
95 19 1
93 20 1
95 9 0
99 7 0
94 18 1
98 8 0
19
94 1 0
100 19 1
95 20 0
93 9 0
98 16 1
100 10 1
98 15 1
99 4 1
94 13 1
100 6 0
97 7 1
100 18 0
92 5 0
100 17 1
96 11 0
97 12 0
95 8 1
92 14 1
92 3 1
4
98 20 1
95 4 0
97 12 1
99 15 1
5
99 15 0
94 11 1
94 16 0
99 20 1
95 5 0
3
94 6 0
99 14 1
94 16 0
3
97 16 1
96 18 0
97 2 0

输出

说明/提示

【样例解释 #1】

最优方案： $(1, 3), (1, 2), (2, 3)$ 为黑色； $(1, 1), (2, 1), (2, 2)$ 为白色。

【数据范围】

测试点编号	$n, m \leq$	$k_{i} \leq$
$1 \sim 2$	$5$	$50$
$3 \sim 5$	$18$	$2$
$6 \sim 8$	$18$	$50$
$9 \sim 10$	$100$	$2$
$11 \sim 12$	$100$	$50$
$13 \sim 16$	$500$	$2$
$17 \sim 20$	$500$	$50$

对于所有数据， $2 \leq n, m \leq 500$ ， $1 \leq T \leq 50$ ， $1 \leq k_{i} \leq min {2 (n + m), 50}$ ， $1 \leq \sum_{i = 1}^{T} k_{i} \leq 50$ ， $0 \leq x \leq 10^{6}$ ， $1 \leq p \leq 2 (n + m)$ ， $t \in {0, 1}$ 。

保证对于每个 $i \in [1, T]$ ， $p_{i, j}$ 互不相同。

【感谢 hack 数据提供】
@_Enthalpy。

s02272. CSP-S 2021 复赛 T4 交通规划 未做

题目描述

题目描述

输入格式

输出格式

样例

说明/提示

s02272. CSP-S 2021 复赛 T4 交通规划未做