covering-chessboard
Source: hackerearth
Difficulty: MEDIUM_HARD

You have an n by m grid. Each grid square has a certain value associated with it. This is given by the numbers vi,j.

You can capture grid squares in two different ways.
You can directly capture a grid square. This costs ci,j.
 You can indirectly capture a grid square. You can only do this if we have already captured all of this squares neighbors. This costs bi,j ≤ ci,j.

Two squares are neighbors if they share an edge.

Your score is the sum of values you have captured minus the cost it took to capture those squares.
Return the maximum possible score you can achieve.

 Input format: 
The first line of input will contain two integers n, m.

The next n lines of input will contain m space separated integers each.
The j-th number on the i-th line denotes vi,j.

The next n lines of input will contain m space separated integers each.
The j-th number on the i-th line denotes bi,j.

The next n lines of input will contain m space separated integers each.
The j-th number on the i-th line denotes ci,j.

 Output format: 
Print a single integer, the answer to the problem.

 Constraints 
For all subtasks:
0 ≤ vi,j ≤ 100,000 
0 ≤ bi,j ≤ ci,j ≤ 100,000 
1 ≤ n, m

 Subtask 1 (45 pts): 
n, m ≤ 3

 Subtask 2 (35 pts): 
n, m ≤ 7

 Subtask 3 (20 pts): 
n, m ≤ 25

SAMPLE INPUT
3 5
9 0 3 2 4
0 2 8 6 2
5 3 4 1 3
5 1 7 9 5
2 4 1 2 4
9 1 2 2 0
9 1 8 9 7
2 7 3 2 9
9 1 9 8 2

SAMPLE OUTPUT
13

Explanation

A more human-readable version of the input is as follows:

3 5
9 0 3 2 4
0 2 8 6 2
5 3 4 1 3

5 1 7 9 5
2 4 1 2 4
9 1 2 2 0

9 1 8 9 7
2 7 3 2 9
9 1 9 8 2

The optimal strategy in this case is to directly capture the following squares:

O X O O O
X O X X O
O X O O X

And indirectly capture only the top left square.


import sys
from collections import deque
from collections import OrderedDict as dict 

INFINITE = 999999999999

global_edges = set()
def solve():
	r, c = list(map(int, sys.stdin.readline().split()))
	val = []
	indirect = []
	direct = []
	for array in [val, indirect, direct]:
		for row in range(r):
			array.append(list(map(int, sys.stdin.readline().split())))
	print(solve_single(val, indirect, direct, r, c))

def solve_single(val, indirect, direct, row, col):
	source = GraphNode('src')
	sink = GraphNode('sink')

	total_possible = 0
	nodes_p = []
	nodes_s = []
	for r in range(row):
		col_list_p = []
		col_list_s = []
		for c in range(col):
			col_list_p.append(GraphNode("({0}, {1})*".format(r, c)))
			col_list_s.append(GraphNode("({0}, {1})**".format(r, c)))
			total_possible += val[r][c]
		nodes_p.append(col_list_p)
		nodes_s.append(col_list_s)

	for r in range(row):
		for c in range(col):
			n1 = nodes_p[r][c]
			n2 = nodes_s[r][c]
			add_edge(n1, n2, val[r][c])
			if (r % 2) == (c % 2):
				add_edge(source, n1, direct[r][c])
				add_edge(n2, sink, indirect[r][c])
				for plus in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
					x, y = plus
					n_x = c + x
					n_y = r + y
					if n_x >= 0 and n_x < col and n_y >= 0 and n_y < row :
						add_edge(n1, nodes_p[n_y][n_x], INFINITE)
						add_edge(n2, nodes_s[n_y][n_x], INFINITE)
			else:
				add_edge(source, n1, indirect[r][c])
				add_edge(n2, sink, direct[r][c])

	while mod_bfs(source, sink):
		pass

	return total_possible - calculate_cut(source)

class GraphNode(object):
	def __init__(self, label):
		self.label = label
		self.connections = dict()
		self.residuals = dict()

	def __repr__(self):
		return self.label

class GraphEdge(object):
	def __init__(self, source, destination, direct_weight):
		self.source = source
		self.destination = destination
		self.direct_weight = direct_weight 
		self.orig_weight = direct_weight
		self.residual_weight = 0
	def __repr__(self):
		return "src: {0}, dest: {1}, dw: {2}, rw: {3}\n".format(self.source, self.destination, self.direct_weight, self.residual_weight)

def add_edge(source, destination, direct_weight):
	ge = GraphEdge(source, destination, direct_weight)
	source.connections[destination] = ge
	destination.residuals[source] = ge
	global_edges.add(ge)
	return ge

def mod_bfs(sourceNode, sinkNode):
	RESIDUAL = True
	DIRECT = False

	visited = set()
	visited.add(sourceNode)
	queue = deque()
	for element in sourceNode.connections:
		connection = sourceNode.connections[element]
		if connection.direct_weight > 0:
			queue.append((connection.destination, connection.direct_weight, [(sourceNode, DIRECT)]))

	while len(queue) > 0:
		node, weight, his = queue.popleft()
		history = list(his)
		if node == sinkNode:
			history.append((node, DIRECT))
			for index in range(len(history)-1):
				node, typed = history[index]
				next_node, next_typed = history[index + 1]
				if typed == RESIDUAL:
					edge = node.residuals[next_node]
					edge.residual_weight -= weight
					edge.direct_weight += weight
				elif typed == DIRECT:
					edge = node.connections[next_node]
					edge.direct_weight -= weight
					edge.residual_weight += weight
			return True
		else:
			for element in node.connections:
				connection = node.connections[element]
				if connection.direct_weight > 0 and connection.destination not in visited:
					min_weight = weight if weight < connection.direct_weight else connection.direct_weight
					new_history = list(history)
					new_history.append((node, DIRECT))
					queue.append((connection.destination, min_weight, new_history))
					visited.add(connection.destination)
			for element in node.residuals:
				connection = node.residuals[element]
				if connection.residual_weight > 0 and connection.source not in visited:
					min_weight = weight if weight < connection.residual_weight else connection.residual_weight
					new_history = list(history)
					new_history.append((node, RESIDUAL))
					queue.append((connection.source, min_weight, new_history))
					visited.add(connection.source)
	return False

def calculate_cut(source):
	cut = 0
	visited = set()
	queue = deque()
	queue.append(source)
	visited.add(source)
	while len(queue) > 0:
		node = queue.popleft()
		for element in node.connections:
			connection = node.connections[element]
			if connection.destination not in visited and connection.direct_weight > 0:
				visited.add(connection.destination)
				queue.append(connection.destination)
		for element in node.residuals:
			connection = node.residuals[element]
			if connection.source not in visited and connection.residual_weight > 0:
				visited.add(connection.source)
				queue.append(connection.source)
	for node in visited:
		for element in node.connections:
			if element not in visited:
				cut += node.connections[element].residual_weight
	return cut

solve()