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

以下是一个Python实现：

from collections import deque

m, n = map(int, input().split())
grid = []
for i in range(m):
    row = list(map(int, input().split()))
    grid.append(row)

# 计算每个格子的编号
id_map = [[0] * n for _ in range(m)]
cnt = 0
for i in range(m):
    for j in range(n):
        id_map[i][j] = cnt
        cnt += 1

# 定义网络流图的源点、汇点，以及每个格子的容量
s = m*n
t = m*n + 1
cap = [[0] * (m*n+2) for _ in range(m*n+2)]
for i in range(m):
    for j in range(n):
        if (i+j) % 2 == 0:  # 如果格子的行列坐标之和为偶数，则该格子为左侧节点
            cap[s][id_map[i][j]] = grid[i][j]  # 源点到左侧节点的容量为格子的值
            for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                x, y = i+dx, j+dy
                if 0 <= x < m and 0 <= y < n:  # 左侧节点向右侧节点连边，容量为无穷大
                    cap[id_map[i][j]][id_map[x][y]] = float('inf')
        else:  # 如果格子的行列坐标之和为奇数，则该格子为右侧节点
            cap[id_map[i][j]][t] = grid[i][j]  # 右侧节点到汇点的容量为格子的值

# 使用BFS算法找到增广路径
def bfs():
    queue = deque([s])
    visited = [False] * (m*n+2)
    visited[s] = True
    parent = [-1] * (m*n+2)
    while queue:
        u = queue.popleft()
        for v in range(m*n+2):
            if not visited[v] and cap[u][v] > 0:
                visited[v] = True
                parent[v] = u
                queue.append(v)
                if v == t:  # 找到增广路径
                    path = []
                    while v != s:
                        path.append(v)
                        v = parent[v]
                    path.append(s)
                    path.reverse()
                    return path
    return None

# 使用Ford-Fulkerson算法求最大流
max_flow = 0
while True:
    path = bfs()
    if not path:
        break
    flow = float('inf')
    for i in range(len(path)-1):
        u, v = path[i], path[i+1]
        flow = min(flow, cap[u][v])
    for i in range(len(path)-1):
        u, v = path[i], path[i+1]
        cap[u][v] -= flow
        cap[v][u] += flow
    max_flow += flow

print(max_flow)

这个算法将每个格子看做一个节点，将源点连接到所有左侧节点，将所有右侧节点连接到汇点。根据题目要求，任意 2 个数所在方格没有公共边，因此可以将相邻的格子拆成左右两个节点，并在左侧节点向右侧节点连边，容量为无穷大。这样就可以将问题转化为一个二分图最大权匹配问题。

具体来说，如果格子的行列坐标之和为偶数，则该格子为左侧节点，源点向左侧节点连边，容量为格子的值；如果格子的行列坐标之和为奇数，则该格子为右侧节点，右侧节点向汇点连边，容量为格子的值。

然后使用标准的Ford-Fulkerson算法求解最大流，即可得到答案。