网络流算法解方格取数问题python： 在一个有m×n个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。 输入：第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。

以下是Python代码实现：

from collections import deque
from typing import List, Tuple

INF = float('inf')


class Graph:
    def __init__(self, n: int):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.cap = [[0] * n for _ in range(n)]

    def add_edge(self, u: int, v: int, w: int) -> None:
        self.adj[u].append(v)
        self.adj[v].append(u)
        self.cap[u][v] += w

    def bfs(self, s: int, t: int) -> Tuple[bool, List[int]]:
        q = deque([s])
        visited = [False] * self.n
        visited[s] = True
        prev = [-1] * self.n
        while q:
            u = q.popleft()
            for v in self.adj[u]:
                if not visited[v] and self.cap[u][v] > 0:
                    visited[v] = True
                    prev[v] = u
                    if v == t:
                        return True, prev
                    q.append(v)
        return False, prev

    def max_flow(self, s: int, t: int) -> int:
        res = 0
        while True:
            has_path, prev = self.bfs(s, t)
            if not has_path:
                break
            min_flow = INF
            u = t
            while u != s:
                min_flow = min(min_flow, self.cap[prev[u]][u])
                u = prev[u]
            u = t
            while u != s:
                self.cap[prev[u]][u] -= min_flow
                self.cap[u][prev[u]] += min_flow
                u = prev[u]
            res += min_flow
        return res


def max_score(board: List[List[int]]) -> int:
    m, n = len(board), len(board[0])
    g = Graph(2 * m * n + 2)
    s, t = 2 * m * n, 2 * m * n + 1
    for i in range(m):
        for j in range(n):
            u = i * n + j
            if (i + j) % 2 == 0:  # 白色节点
                g.add_edge(s, u, board[i][j])
                g.add_edge(u, u + m * n, INF)  # 选择节点
                if i > 0:
                    v = (i - 1) * n + j
                    g.add_edge(u + m * n, v, INF)
                if j > 0:
                    v = i * n + j - 1
                    g.add_edge(u + m * n, v, INF)
                if i < m - 1:
                    v = (i + 1) * n + j
                    g.add_edge(u + m * n, v, INF)
                if j < n - 1:
                    v = i * n + j + 1
                    g.add_edge(u + m * n, v, INF)
            else:  # 黑色节点
                g.add_edge(u, t, board[i][j])
                g.add_edge(u + m * n, u, INF)  # 选择节点
    return g.max_flow(s, t)

使用示例：

board = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(max_score(board))  # 输出15