P7916 [CSP-S 2021] Traffic Planning

Given $n$ horizontal lines and $m$ vertical lines on a plane, they intersect to form a grid with $n$ rows and $m$ columns. The intersection point between the $r$-th horizontal line from top to bottom and the $c$-th vertical line from left to right is called the grid point $(r, c)$. In the grid, the segment between any two horizontally or vertically adjacent grid points is called an edge, and each edge has a non-negative integer weight. There are $T$ queries. Each query is as follows: You are given $k$ (the value of $k$ may differ among the $T$ queries) additional points. Each additional point lies on a ray that starts from the border of the grid and goes outward. All rays starting from the border of the grid are numbered from $1$ to $2 n + 2 m$ in the order top-left $\to$ top-right $\to$ bottom-right $\to$ bottom-left $\to$ top-left, as shown in the figure:  For each query, the rays on which different additional points lie are all distinct. The segment between each additional point and its nearest grid point is also called an edge, and it also has a non-negative integer weight (note that a corner grid point may be connected to two additional points at the same time). Given the color (black or white) of each additional point, you need to color every grid point in the grid either black or white, so that the sum of weights of all edges whose endpoints have different colors is minimized. Output this minimum sum of edge weights.

The first line contains three positive integers $n, m, T$, representing the numbers of horizontal and vertical lines, and the number of queries. The next $n - 1$ lines each contain $m$ non-negative integers. The $j$-th non-negative integer in the $i$-th line ${x 1}_{i, j}$ denotes the weight of the edge between $(i, j)$ and $(i + 1, j)$. The next $n$ lines each contain $m - 1$ non-negative integers. The $j$-th non-negative integer in the $i$-th line ${x 2}_{i, j}$ denotes the weight of the edge between $(i, j)$ and $(i, j + 1)$. Then follow $T$ groups of queries. In the $i$-th group, the first line contains a positive integer $k_i$, denoting the total number of additional points in this query. The next $k_i$ lines each contain three non-negative integers. In the $j$-th line, ${x 3}_{i, j}, p_{i, j}, t_{i, j}$ denote the weight of the edge between the $j$-th additional point and its adjacent grid point, the index of the ray it lies on, and the color of the additional point ($0$ for white, $1$ for black). It is guaranteed that within the same query group, all $p_{i, j}$ are distinct. Multiple integers on the same line are separated by spaces.

Output $T$ lines. The $i$-th line contains a non-negative integer, denoting the minimum possible sum of weights of edges whose endpoints have different colors after coloring for the $i$-th query.

**Sample Explanation #1** An optimal solution: $(1, 3), (1, 2), (2, 3)$ are black; $(1, 1), (2, 1), (2, 2)$ are white. **Constraints** | Test Point ID | $n, m \le$ | $k_i \le$ | |:-:|:-:|:-:| | $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$ | For all data, $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 \}$. It is guaranteed that for each $i \in [1, T]$, all $p_{i, j}$ are distinct. [Thanks for providing hack testdata] @[\_Enthalpy](/user/42156)。 Translated by ChatGPT 5