#P10373. [2021年联测]傅里叶与电极

    ID: 9491 传统题 1000ms 888MiB 尝试: 9 已通过: 1 难度: 6 上传者: 标签>CF2000提高最小割建模Dinic最大流最小割定理当前弧优化

[2021年联测]傅里叶与电极

题目描述

给定一个 n×mn\times m 的矩阵 hh,其中 hx,yh_{x,y} 表示位置 (x,y)(x,y) 的电场强度,可以为负数。有 pp 个彼此不同的位置 (xi,yi)(x_i,y_i) 可以放置电极。对第 ii 个电极,独立选择强度 ωi=+wi\omega_i=+w_i 或 ωi=−wi\omega_i=-w_i。

单个电极的贡献为 hxi,yiωih_{x_i,y_i}\omega_i。若两个电极所在格子共边相邻,则另有一次贡献 ωiωj\omega_i\omega_j,同一对电极只计一次。实际效果为全部贡献之和。

求实际效果的最大值。

输入格式

第一行一个整数 TT,表示数据组数。每组数据先输入三个整数 n,m,pn,m,p,随后 nn 行每行 mm 个整数,给出矩阵 hh。接下来 pp 行,第 ii 行三个整数 xi,yi,wix_i,y_i,w_i。

输出格式

每组数据输出一行一个整数,表示最大实际效果。

样例

1
2 2 3
1 4
-1 -2
1 1 3
1 2 1
2 2 2
12

取电极符号为 +,+,−+,+,- 可达到 1212。原 PDF 样例额外列出的这组符号用于说明,评测输出只有最大值。

数据范围

  • 30%30\% 的数据满足 p≤15p\le15。
  • 另外 30%30\% 的数据满足 n≤2n\le2。
  • 所有数据满足 1≤T≤101\le T\le10,1≤p≤2001\le p\le200,1≤n,m≤10001\le n,m\le1000,1≤xi≤n1\le x_i\le n,1≤yi≤m1\le y_i\le m,∣hi,j∣≤1000|h_{i,j}|\le1000,∑nm≤106\sum nm\le10^6。电极位置互不相同。
  • 原 PDF 给出的强度上界为 100100,本站现有评测中 0≤wi≤2000\le w_i\le200。

原 PDF 题面