题目描述
给定一个 n×m 的矩阵 h,其中 hx,y 表示位置 (x,y) 的电场强度,可以为负数。有 p 个彼此不同的位置 (xi,yi) 可以放置电极。对第 i 个电极,独立选择强度 ωi=+wi 或 ωi=−wi。
单个电极的贡献为 hxi,yiωi。若两个电极所在格子共边相邻,则另有一次贡献 ωiωj,同一对电极只计一次。实际效果为全部贡献之和。
求实际效果的最大值。
输入格式
第一行一个整数 T,表示数据组数。每组数据先输入三个整数 n,m,p,随后 n 行每行 m 个整数,给出矩阵 h。接下来 p 行,第 i 行三个整数 xi,yi,wi。
输出格式
每组数据输出一行一个整数,表示最大实际效果。
样例
1
2 2 3
1 4
-1 -2
1 1 3
1 2 1
2 2 2
12
取电极符号为 +,+,− 可达到 12。原 PDF 样例额外列出的这组符号用于说明,评测输出只有最大值。
数据范围
- 30% 的数据满足 p≤15。
- 另外 30% 的数据满足 n≤2。
- 所有数据满足 1≤T≤10,1≤p≤200,1≤n,m≤1000,1≤xi≤n,1≤yi≤m,∣hi,j∣≤1000,∑nm≤106。电极位置互不相同。
- 原 PDF 给出的强度上界为 100,本站现有评测中 0≤wi≤200。
原 PDF 题面