Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Consider a grid with $H$ rows (numbered $1$ through $H$) and $W$ columns (numbered $1$ through $W$). Let's denote the value in a cell in row $i$ and column $j$ by $h_{i,j}$. $N$ particles (numbered $1$ through $N$) are distributed in the cells in such a way that there is at most one particle in each cell. For each valid $i$, the $i$-th particle has a value $p_{i}$ and it is placed in the cell in row $y_{i}$ and column $x_{i}$.

Let's denote the set of all particles by $P$ and the set of all unordered pairs of particles that are located in side-adjacent cells by $E$. We define the value of the grid as
$$V = \sum_{i \in P} p_{i} \cdot h_{y_{i},x_{i}} + \sum_{(i,j) \in E} p_{i} \cdot p_{j} \,.$$

You are given the grid and the locations of all particles, but not their exact values ― only $\lvert p_{1} \rvert, \lvert p_{2} \rvert, \ldots, \lvert p_{N} \rvert$. Your task is to choose the sign of each value $p_{i}$ in such a way that the value $V$ is maximum possible. Each sign may be chosen independently from all other signs.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains three space-separated integers $H$, $W$ and $N$.
$H$ lines follow. For each valid $i$, the $i$-th of these lines contains $W$ space-separated integers $h_{i,1}, h_{i,2}, \ldots, h_{i,W}$.
$N$ more lines follow. For each valid $i$, the $i$-th of these lines contains three space-separated integers $y_{i}$, $x_{i}$ and $\lvert p_{i} \rvert$.

------  Output ------
For each test case, print two lines.
The first of these lines should contain a single integer ― the maximum value of $V$.
The second line should contain $N$ space-separated integers. For each valid $i$, the $i$-th of these integers should be $1$ if you choose a positive sign for the value of the $i$-th particle (i.e. its value should be $\lvert p_{i} \rvert$) or $-1$ if you choose a negative sign (i.e. its value should be $-\lvert p_{i} \rvert$).

If there are multiple solutions, you may find any one.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ H, W ≤ 1,000$
$1 ≤ N ≤ 200$
$\lvert h_{i,j} \rvert ≤ 1,000$ for each valid $i, j$
$1 ≤ y_{i} ≤ H$ for each valid $i$
$1 ≤ x_{i} ≤ W$ for each valid $i$
$\lvert p_{i} \rvert ≤ 100$ for each valid $i$
no two particles are located in the same cell
the sum of $H \cdot W$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (10 points): $N ≤ 15$

Subtask #2 (20 points): $H ≤ 2$

Subtask #3 (70 points): original constraints

----- Sample Input 1 ------ 
1

2 2 3

1 4

-1 -2

1 1 3

1 2 1

2 2 2
----- Sample Output 1 ------ 
12

1 1 -1

Source: codechef | Difficulty: VERY_HARD
Tags: Data structures

Graph algorithms

Graph traversal

Flows and cuts


Solutions:
from sys import stdin

class Edge:

	def __init__(self, to, rev, f, cap):
		self.to = to
		self.rev = rev
		self.f = f
		self.cap = cap

class DinicsAlgo:

	def __init__(self, N):
		self.dist = [-1] * N
		self.q = [0] * N
		self.g = [[] for i in range(N)]

	def add_edge(self, s, t, cap):
		a = Edge(s, len(self.g[s]), 0, cap)
		b = Edge(t, len(self.g[t]), 0, cap)
		self.g[s].append(b)
		self.g[t].append(a)

	def bfs(self, N):
		self.dist = [-1] * N
		self.dist[0] = 0
		qsz = 0
		self.q[qsz] = self.src
		qsz += 1
		i = 0
		while i < qsz:
			u = self.q[i]
			i += 1
			for e in self.g[u]:
				v = e.to
				if self.dist[v] < 0 and e.f < e.cap:
					self.dist[v] = self.dist[u] + 1
					self.q[qsz] = v
					qsz += 1
		return self.dist[self.dest] >= 0

	def dfs(self, u, f):
		if u == self.dest:
			return f
		for e in self.g[u]:
			if e.cap <= e.f:
				continue
			v = e.to
			if self.dist[v] == self.dist[u] + 1:
				df = self.dfs(v, min(f, e.cap - e.f))
				if df > 0:
					e.f += df
					self.g[v][e.rev].f -= df
					return df
		return 0

	def mf(self, s, t, N):
		self.src = s
		self.dest = t
		ret = 0
		while self.bfs(N):
			delta = self.dfs(s, 1000000000)
			while delta:
				ret += delta
				delta = self.dfs(s, 1000000000)
		return ret

def dfs_up(node, G):
	up[node] = 1
	for e in G.g[node]:
		if e.cap > e.f and up[e.to] == -1:
			dfs_up(e.to, G)
for _ in range(int(stdin.readline())):
	(h, w, n) = map(int, stdin.readline().split())
	arr = [[0] * w]
	for i in range(1, h + 1):
		arr.append([0] + list(map(int, stdin.readline().split())))
	x = [0] * (n + 1)
	y = [0] * (n + 1)
	p = [0] * (n + 1)
	for i in range(1, n + 1):
		(x[i], y[i], p[i]) = map(int, stdin.readline().split())
	G = DinicsAlgo(n + 2)
	V = 0
	for i in range(1, n + 1):
		V += abs(arr[x[i]][y[i]] * p[i])
		if arr[x[i]][y[i]] >= 0:
			G.add_edge(0, i, arr[x[i]][y[i]] * p[i])
		if arr[x[i]][y[i]] < 0:
			G.add_edge(i, n + 1, -arr[x[i]][y[i]] * p[i])
		for j in range(i + 1, n + 1):
			if abs(x[i] - x[j]) + abs(y[i] - y[j]) == 1:
				G.add_edge(i, j, p[i] * p[j])
				V += p[i] * p[j]
	V -= 2 * G.mf(0, n + 1, n + 2)
	up = [-1] * (n + 2)
	dfs_up(0, G)
	print(V)
	for i in range(1, n + 1):
		print(up[i], end=' ')


def min_cut(capacity, src, sink):
	from collections import deque
	N = len(capacity)

	def bfs():
		queue = deque([src])
		parents = {src: -1}
		found = False
		while queue:
			u = queue.popleft()
			if u == sink:
				found = True
				break
			for v in range(N):
				if v not in parents and capacity[u][v] > 0:
					parents[v] = u
					queue.append(v)
		return (found, parents)
	while True:
		(found, parents) = bfs()
		if not found:
			break
		mn = float('inf')
		v = sink
		while parents[v] != -1:
			u = parents[v]
			mn = min(mn, capacity[u][v])
			v = u
		v = sink
		while parents[v] != -1:
			u = parents[v]
			capacity[u][v] -= mn
			capacity[v][u] += mn
			v = u
	queue = deque([src])
	src_nodes = set([src])
	while queue:
		u = queue.popleft()
		for v in range(N):
			if v not in src_nodes and capacity[u][v] > 0:
				src_nodes.add(v)
				queue.append(v)
	return src_nodes

def solve(nr, nc, grid, particles):
	particles = [(r - 1, c - 1, x) for (r, c, x) in particles]
	N = len(particles)
	(pos, neg) = (N, N + 1)
	capacity = [[0] * (N + 2) for _ in range(N + 2)]
	for (i, (r, c, x)) in enumerate(particles):
		if grid[r][c] > 0:
			capacity[pos][i] = x * grid[r][c]
		if grid[r][c] < 0:
			capacity[i][neg] = -x * grid[r][c]
		for j in range(i + 1, len(particles)):
			(rr, cc, xx) = particles[j]
			if r == rr and abs(c - cc) == 1 or (c == cc and abs(r - rr) == 1):
				capacity[i][j] = x * xx
				capacity[j][i] = x * xx
	pos_nodes = min_cut(capacity, pos, neg)
	sign = [1 if u in pos_nodes else -1 for u in range(N)]
	res = 0
	for (i, (r, c, x)) in enumerate(particles):
		res += grid[r][c] * x * sign[i]
		for j in range(i + 1, len(particles)):
			(rr, cc, xx) = particles[j]
			if r == rr and abs(c - cc) == 1 or (c == cc and abs(r - rr) == 1):
				res += x * xx * sign[i] * sign[j]
	return (res, sign)

def main():
	from sys import stdin
	T = int(stdin.readline().strip())
	for t in range(T):
		(H, W, N) = list(map(int, stdin.readline().strip().split()))
		grid = [list(map(int, stdin.readline().strip().split())) for _ in range(H)]
		particles = [list(map(int, stdin.readline().strip().split())) for _ in range(N)]
		(res, sign) = solve(H, W, grid, particles)
		print(res)
		print(' '.join(map(str, sign)))
main()