网络流24题09方格取数问题
时间: 2023-07-27 07:07:15 浏览: 45
方格取数问题是一个典型的网络流问题。我们可以将每个格子看作一个节点,将每个格子向它下面和右边的格子连一条容量为该格子的权值的边,表示从该格子出发的流量。同时,我们还需要对源点和汇点进行建模。将源点向左上角的格子和右下角的格子分别连一条容量为正无穷的边,表示从源点出发的流量只能流向左上角的格子,从右下角的格子只能流向汇点。最后,我们只需要在这个网络流上跑最大流,就可以得到最大权值和。
需要注意的是,这个问题有一个特殊的性质,就是格子的权值非负。因此,我们可以使用最大权闭合子图算法来求解最大流,这个算法的时间复杂度是 $O(V^2)$,比常规的网络流算法要快得多。
相关问题
python实现网络流方格取数问题代码
下面是Python实现网络流方格取数问题的代码示例:
```python
from ortools.graph import pywrapgraph
# 定义方格的大小和初始值
grid_size = 4
grid = [[4, 7, 8, 6], [6, 7, 3, 9], [3, 5, 2, 1], [9, 2, 8, 2]]
# 创建网络流图
max_flow = pywrapgraph.SimpleMaxFlow()
source = 0
sink = grid_size ** 2 + 1
node_num = grid_size ** 2 + 2
# 添加源点和汇点
max_flow.AddNode(node_num)
max_flow.AddArc(source, sink, float('inf'))
# 添加方格中的节点和边
for i in range(grid_size):
for j in range(grid_size):
node_id = i * grid_size + j + 1
max_flow.AddNode(node_num)
max_flow.AddArc(source, node_id, grid[i][j])
if i == 0:
max_flow.AddArc(node_id, sink, 0)
else:
for k in range(grid_size):
next_node_id = (i - 1) * grid_size + k + 1
max_flow.AddArc(node_id, next_node_id, float('inf'))
if j == 0:
max_flow.AddArc(node_id, sink, 0)
else:
for k in range(grid_size):
next_node_id = i * grid_size + k + 1
max_flow.AddArc(node_id, next_node_id, float('inf'))
# 求解最大流
status = max_flow.Solve(source, sink)
if status == max_flow.OPTIMAL:
max_flow_value = max_flow.OptimalFlow()
print('最大取数和为:', max_flow_value)
```
该代码使用了Google OR-Tools库中的`SimpleMaxFlow`模块,实现了方格取数问题的最大流解法。该算法将方格中的每个元素看作一个节点,并且将每个节点与其上、下、左、右的相邻节点之间的边的容量设置为无限大,确保每个节点都可以通过其相邻节点到达汇点。同时,将源点与每个节点之间的边的容量设置为该节点的初始值,保证源点只能向该节点中取出其初始值大小的数。最终通过求解网络流问题,得到了最大取数和。
网络流方格取数问题python代码
下面是一个简单的 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` 函数用于计算方格取数问题的最大和。