#1482. 交通规划

交通规划

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个平面上 n\red n 条水平直线和 m\red m 条垂直直线,它们相交形成 n\red n m\red m 列的网格,从上到下第 r\red r 条水平直线和从左到右第 c\red c 条垂直直线之间的交点称为格点 (r,c\red {r,c})。

网格中任意两个水平或垂直相邻的格点之间的线段称为一条边,每条边有一个非负整数边权。

进行 T\red T 次询问,每次询问形式如下:

给出 k\red kT\red T 次询问的 k\red k 可能不同)个附加点,每个附加点位于一条从网格边缘向外出发的射线上。

所有从网格边缘向外出发的射线按左上 - 右上 - 右下 - 左下 - 左上的顺序依次编号为 1\red 12n+2m\red {2n+2m},如下图:

img

对于每次询问,不同附加点所在的射线互不相同。

每个附加点和最近的格点之间的线段也称为一条边,也有非负整数边权(注意,在角上的格点有可能和两个附加点同时相连)。

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

请输出这个最小的边权和。

输入格式

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

接下来 n1\red {n−1}行,每行 m\red m 个非负整数。

其中第 i\red i 行的第 j\red j 个非负整数 x1i,j\red {x1_{i,j}} 表示 (i,j\red {i,j}) 和 (i+1,j\red {i+1,j}) 间的边权。

接下来 n\red n 行,每行 m1\red {m−1} 个非负整数。

其中第 i\red i 行的第 j\red j 个非负整数 x2i,j\red {x2_{i,j}} 表示 (i,j\red {i,j}) 和 (i,j+1\red {i,j+1}) 间的边权。

接下来依次输入 T\red T 组询问。

i\red i 组询问开头为一行一个正整数 ki\red {k_i} 表示这次询问附加点的总数。

接下来 ki\red {k_i}行每行三个非负整数。

其中第 j\red j 行依次为 x3i,j,pi,j,ti,j\red {x3_{i,j},p_{i,j},t_{i,j}} 表示第 j\red j 个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色(0\red 0 为白色,1\red 1 为黑色)。

保证同一组询问内 pi,j\red {p_{i,j}} 互不相同。

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

输出格式

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

输入输出样例

输入样例1

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

输出样例1

12

说明/提示

样例解释

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

【数据范围】

测试点编号 n,m\red {n,m ≤} ki\red {k_i≤}
12\red {1∼2 } 5\red { 5 } 50\red { 50}
35\red {3∼5 } 18\red { 18 } 2\red { 2 }
68\red {6∼8 } 50\red { 50}
910\red {9∼10 } 100\red { 100} 2\red { 2 }
1112\red {11∼12} 50\red { 50}
1316\red {13∼16} 500\red { 500} 2\red { 2 }
1720\red {17∼20} 50\red { 50}

对于所有数据,2n,m500\red {2≤n,m≤500}1T50\red {1≤T≤50}1kimin{2(n+m),50}\red {1≤k_i ≤ min⁡\{2(n+m),50\}}1i=1Tki50\red {1≤ \sum _{i=1}^{T} k_i≤50}0x106\red {0≤x≤10^6}1p2(n+m)\red {1≤p≤2(n+m)}t{0,1}\red {t∈\{0,1\} }

保证对于每个 i[1,T]pi,j\red {i∈[1,T],p_{i,j}} 互不相同。

2020年CSP-S第二轮重现

未参加
状态
已结束
规则
IOI
题目
4
开始于
2023-10-11 9:45
结束于
2023-10-19 17:45
持续时间
200 小时
主持人
参赛人数
15