#85. 交通规划

交通规划

题目描述

给定一个平面上 nn 条水平直线和 mm 条垂直直线,它们相交形成 nnmm 列的网格,从上到下第 rr 条水平直线和从左到右第 cc 条垂直直线之间的交点称为格点 (r,c)(r, c)。网格中任意两个水平或垂直相邻的格点之间的线段称为一条边,每条边有一个非负整数边权。 进行 TT 次询问,每次询问形式如下: 给出 kkTT 次询问的 kk 可能不同)个附加点,每个附加点位于一条从网格边缘向外出发的射线上。所有从网格边缘向外出发的射线按左上-右上-右下-左下-左上的顺序依次编号为 112n+2m2n + 2m,如下图:

图2: 射线的编号

对于每次询问,不同附加点所在的射线互不相同。每个附加点和最近的格点之间的线段也称为一条边,也有非负整数边权(注意,在角上的格点有可能和两个附加点同时相连)。 给定每个附加点的颜色(黑色或者白色),请你将网格内每个格点的颜色染成黑白二者之一,并使得所有两端颜色不同的边的边权和最小。请输出这个最小的边权和。

输入格式

从文件 traffic.in 中读入数据。 第一行 33 个正整数 n,m,Tn, m, T 分别表示水平、垂直直线的数量,以及询问次数。 接下来 n1n − 1 行,每行 mm 个非负整数。其中第 ii 行的第 jj 个非负整数 x1i,jx1_{i,j} 表示 (i,j)(i, j)(i+1,j)(i + 1, j) 间的边权。 接下来 nn 行,每行 m1m − 1 个非负整数。其中第 ii 行的第 jj 个非负整数 x2i,jx2_{i,j} 表示 (i,j)(i, j)(i,j+1)(i, j + 1) 间的边权。 接下来依次输入 TT 组询问。第 ii 组询问开头为一行一个正整数 kik_i 表示这次询问附加点的总数。接下来 kik_i 行每行三个非负整数。其中第 jj 行依次为 x3i,j,pi,j,ti,jx3_{i,j}, p_{i,j}, t_{i,j} 表示第 ii 个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色(00 为白色,11 为黑色)。保证同一组询问内 pi,jp_{i,j} 互不相同。 每行的多个整数由空格分隔。

输出格式

输出到文件 traffic.out 中。 输出 TT 行,第 ii 行输出一个非负整数,表示第 ii 次询问染色之后两端颜色不同的边 权和的最小值。

2 3 1
9 4 7
3 8
10 5
2
19 3 1
17 9 0
12

样例 1 解释

最优方案:(1,3),(1,2),(2,3)(1, 3), (1, 2), (2, 3) 为黑色;(1,1),(2,1),(2,2)(1, 1), (2, 1), (2, 2) 为白色。

样例 2

见选手目录下的 traffic2.intraffic2.ans

样例 3

见选手目录下的 traffic3.intraffic3.ans

样例 4

见选手目录下的 traffic4.intraffic4.ans

数据范围与提示

测试点编号 n,mn, m\le kik_i \leq
1,21,2 55 5050
3,4,53,4,5 1818 22
6,7,86,7,8 5050
9,109,10 10210^2 22
11,1211,12 5050
13,14,15,1613,14,15,16 500500 22
17,18,19,2017,18,19,20 5050

对于所有数据,$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[1,T]i \in [1, T]pi,jp_{i,j} 互不相同。