<p>You are given a <code>m x n</code> 2D array <code>board</code> representing a chessboard, where <code>board[i][j]</code> represents the <strong>value</strong> of the cell <code>(i, j)</code>.</p>

<p>Rooks in the <strong>same</strong> row or column <strong>attack</strong> each other. You need to place <em>three</em> rooks on the chessboard such that the rooks <strong>do not</strong> <strong>attack</strong> each other.</p>

<p>Return the <strong>maximum</strong> sum of the cell <strong>values</strong> on which the rooks are placed.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = </span>[[-3,1,1,1],[-3,1,-3,1],[-3,2,1,1]]</p>

<p><strong>Output:</strong> 4</p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/08/08/rooks2.png" style="width: 294px; height: 450px;" /></p>

<p>We can place the rooks in the cells <code>(0, 2)</code>, <code>(1, 3)</code>, and <code>(2, 1)</code> for a sum of <code>1 + 1 + 2 = 4</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = [[1,2,3],[4,5,6],[7,8,9]]</span></p>

<p><strong>Output:</strong> <span class="example-io">15</span></p>

<p><strong>Explanation:</strong></p>

<p>We can place the rooks in the cells <code>(0, 0)</code>, <code>(1, 1)</code>, and <code>(2, 2)</code> for a sum of <code>1 + 5 + 9 = 15</code>.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = [[1,1,1],[1,1,1],[1,1,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>We can place the rooks in the cells <code>(0, 2)</code>, <code>(1, 1)</code>, and <code>(2, 0)</code> for a sum of <code>1 + 1 + 1 = 3</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= m == board.length &lt;= 500</code></li>
	<li><code>3 &lt;= n == board[i].length &lt;= 500</code></li>
	<li><code>-10<sup>9</sup> &lt;= board[i][j] &lt;= 10<sup>9</sup></code></li>
</ul>

# Modified from https://cp-algorithms.com/graph/min_cost_flow.html

import dataclasses

@dataclasses.dataclass
class Edge:
    residualCapacity: int
    cost: int

class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        m = len(board)
        n = len(board[0])

        rowOffset = 1
        colOffset = rowOffset + m
        sink = colOffset + n
        size = sink + 1
        
        adjDict = [{} for _ in range(size)]
        
        for i, row in enumerate(board):
            rowIndex = rowOffset + i

            adjDict[0][rowIndex] = Edge(1, 0)
            adjDict[rowIndex][0] = Edge(0, 0)
            for j, element in enumerate(row):
                colIndex = colOffset + j

                adjDict[rowIndex][colIndex] = Edge(1, -element)
                adjDict[colIndex][rowIndex] = Edge(0, element)
        
        for i in range(colOffset, colOffset + n):
            adjDict[i][sink] = Edge(1, 0)
            adjDict[sink][i] = Edge(0, 0)
        
        flow = 0
        cost = 0
        while flow < 3:
            # SPFA
            d = [inf] * size
            d[0] = 0

            p = [0] * size

            q = deque((0,))
            inq = [False] * size
            while q:
                u = q.popleft()
                inq[u] = False

                for v, edge in adjDict[u].items():
                    if edge.residualCapacity > 0 and d[v] > d[u] + edge.cost:
                        d[v] = d[u] + edge.cost
                        p[v] = u
                        if not inq[v]:
                            inq[v] = True
                            q.append(v)
            
            f = 3 - flow
            cur = sink
            while cur != 0:
                f = min(f, adjDict[p[cur]][cur].residualCapacity)
                cur = p[cur]
            
            flow += f
            cost += f * d[sink]
            cur = sink
            while cur != 0:
                adjDict[p[cur]][cur].residualCapacity -= f
                adjDict[cur][p[cur]].residualCapacity += f
                cur = p[cur]
        
        return -cost

88014