问题 D: [CSP-S 2021] 交通规划
传统题
3.000s
时间限制
512MB
内存限制
0 提交
0 解决
【题目描述】
## 题目描述给定一个平面上 n 条水平直线和 m 条垂直直线，它们相交形成 n行 m 列的网格，从上到下第 r 条水平直线和从左到右第 c 条垂直直线之间的交点称为格点 (r, c)。网格中任意两个水平或垂直相邻的格点之间的线段称为一条边，每条边有一个非负整数边权。
进行 T 次询问，每次询问形式如下：
给出 k（T 次询问的 k 可能不同）个附加点，每个附加点位于一条从网格边缘向外出发的射线上。所有从网格边缘向外出发的射线按左上-右上-右下-左下-左上的顺序依次编号为 1 到 2n + 2m，如下图：
对于每次询问，不同附加点所在的射线互不相同。每个附加点和最近的格点之间的线段也称为一条边，也有非负整数边权（注意，在角上的格点有可能和两个附加点同时相连）。
给定每个附加点的颜色（黑色或者白色），请你将网格内每个格点的颜色染成黑白二者之一，并使得所有两端颜色不同的边的边权和最小。请输出这个最小的边权和。
## 输入格式
第一行，三个正整数 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 行依次为 x3i, j, pi, j, ti, j 表示第 j 个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色（0 为白色，1 为黑色）。保证同一组询问内 pi, j 互不相同。
每行的多个整数由空格分隔。
## 输出格式
输出 T 行，第 i 行输出一个非负整数，表示第 i 次询问染色之后两端颜色不同的边权和的最小值。
## 样例 #1
### 样例输入 #1
2 3 1
9 4 7
3 8
10 5
2
19 3 1
17 9 0
### 样例输出 #1
12
## 样例 #2
### 样例输入 #2
见附件中的 traffic/traffic2.in
### 样例输出 #2
见附件中的 traffic/traffic2.ans
## 样例 #3
### 样例输入 #3
见附件中的 traffic/traffic3.in
### 样例输出 #3
见附件中的 traffic/traffic3.ans
## 样例 #4
### 样例输入 #4
见附件中的 traffic/traffic4.in
### 样例输出 #4
见附件中的 traffic/traffic4.ans
## 样例 #5
### 样例输入 #5
见附件中的 traffic/traffic5.in
### 样例输出 #5
见附件中的 traffic/traffic5.ans
## 提示
**【样例解释 #1】**
最优方案：(1, 3), (1, 2), (2, 3) 为黑色；$(1, 1), (2, 1), (2, 2) 为白色。
**【数据范围】**
|
测试点编号
|
n,m≤
|
Ki≤
|
|
1~2
|
5
|
50
|
|
3~5
|
18
|
2
|
|
6~8
|
18
|
50
|
|
9~10
|
100
|
2
|
|
11~12
|
100
|
50
|
|
13~16
|
500
|
2
|
|
17~20
|
500
|
50
|
对于所有数据，2≤n, m≤500，1≤T≤50，1≤ki≤min{2(n + m), 50 }，1≤
≤50$，0≤x≤106，1 ≤p≤2(n + m)，t ∈{ 0, 1}。
保证对于每个 i ∈ [1, T]，pi, j 互不相同。