[CSP-S 2021] 交通规划

题目描述

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

进行 $T$ 次询问。每次询问给出 $k$ 个附加点，每个附加点位于一条从网格边缘向外出发的射线上。所有射线按左上、右上、右下、左下、左上的顺序编号为 $1$ 到 $2n+2m$。同一次询问中，不同附加点所在射线互不相同。

每个附加点与最近的格点之间也有一条带权边。给定每个附加点的颜色（黑色或白色），你需要将网格内每个格点染成黑白二者之一，使所有两端颜色不同的边的边权和最小。输出该最小边权和。

输入格式

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

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

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

接下来依次输入 $T$ 组询问。每组询问第一行一个正整数 $k_i$，表示本次询问附加点总数；接下来 $k_i$ 行，每行三个非负整数 $x3_{i,j},p_{i,j},t_{i,j}$，分别表示第 $j$ 个附加点与相邻格点之间的边权、所在射线编号以及附加点颜色。$t=0$ 表示白色，$t=1$ 表示黑色。

同一组询问内，所有 $p_{i,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

数据范围与提示

样例 #1 的一种最优方案为：$(1,3),(1,2),(2,3)$ 染为黑色，$(1,1),(2,1),(2,2)$ 染为白色。

数据范围与提示

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

附件下载

traffic.zip