网络流方格取数问题python代码

下面是一个简单的 Python 代码实现方格取数问题的网络流解法：

from collections import deque

# 定义网络流节点
class Node:
    def __init__(self, x, y, val):
        self.x = x
        self.y = y
        self.val = val
        self.in_edges = []
        self.out_edges = []

# 定义网络流边
class Edge:
    def __init__(self, u, v, cap, flow):
        self.u = u
        self.v = v
        self.cap = cap
        self.flow = flow
        self.rev = None

# 构建网络流图
def build_graph(grid):
    n = len(grid)
    m = len(grid[0])
    nodes = [[None] * m for _ in range(n)]
    s = Node(-1, -1, 0)
    t = Node(-2, -2, 0)
    for i in range(n):
        for j in range(m):
            nodes[i][j] = Node(i, j, grid[i][j])
            if (i + j) % 2 == 0:
                # 如果是偶数行，向源点连边
                e = Edge(s, nodes[i][j], nodes[i][j].val, 0)
                e.rev = Edge(nodes[i][j], s, 0, 0)
                e.rev.rev = e
                s.out_edges.append(e)
                nodes[i][j].in_edges.append(e)
            else:
                # 如果是奇数行，向汇点连边
                e = Edge(nodes[i][j], t, nodes[i][j].val, 0)
                e.rev = Edge(t, nodes[i][j], 0, 0)
                e.rev.rev = e
                t.in_edges.append(e)
                nodes[i][j].out_edges.append(e)
            if i > 0:
                # 向上连边
                e = Edge(nodes[i][j], nodes[i-1][j], min(nodes[i][j].val, nodes[i-1][j].val), 0)
                e.rev = Edge(nodes[i-1][j], nodes[i][j], 0, 0)
                e.rev.rev = e
                nodes[i][j].out_edges.append(e)
                nodes[i-1][j].in_edges.append(e)
            if j > 0:
                # 向左连边
                e = Edge(nodes[i][j], nodes[i][j-1], min(nodes[i][j].val, nodes[i][j-1].val), 0)
                e.rev = Edge(nodes[i][j-1], nodes[i][j], 0, 0)
                e.rev.rev = e
                nodes[i][j].out_edges.append(e)
                nodes[i][j-1].in_edges.append(e)
    return nodes, s, t

# 计算最大流
def max_flow(nodes, s, t):
    total_flow = 0
    while True:
        # 使用 BFS 寻找增广路径
        q = deque()
        q.append(s)
        parent = {s: None}
        while q and t not in parent:
            u = q.popleft()
            for e in u.out_edges:
                if e.v not in parent and e.flow < e.cap:
                    parent[e.v] = e
                    q.append(e.v)
            for e in u.in_edges:
                if e.u not in parent and e.flow > 0:
                    parent[e.u] = e.rev
                    q.append(e.u)
        if t not in parent:
            break
        # 计算增广路径上的最小残量
        path_flow = float("inf")
        v = t
        while v != s:
            e = parent[v]
            path_flow = min(path_flow, e.cap - e.flow if e.u == v else e.flow)
            v = e.u if e.u != v else e.v
        # 更新网络流
        v = t
        while v != s:
            e = parent[v]
            if e.u == v:
                e.flow += path_flow
            else:
                e.flow -= path_flow
            v = e.u if e.u != v else e.v
        total_flow += path_flow
    return total_flow

# 方格取数问题的解法
def max_sum(grid):
    nodes, s, t = build_graph(grid)
    max_flow(nodes, s, t)
    return sum(nodes[i][j].val for i in range(len(nodes))
               for j in range(len(nodes[0]))
               if (i + j) % 2 == 0 and nodes[i][j] in s.out_edges)

其中，`build_graph` 函数用于构建网络流图，`max_flow` 函数用于计算最大流，`max_sum` 函数用于计算方格取数问题的最大和。