网络流算法实践(python):方格取数问题: 在一个有m×n个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。 输入:第 1 行有 2 个正整数 m 和 n,分别表示棋盘的行数和列数。接下来的 m 行,每行有 n 个正整数,表示棋盘方格中的数。 输入样例: 3 3 1 2 3 3 2 3 2 3 1 输出:程序运行结束时,将取数的最大总和输出 输出样例: 11并给出问题分析、 算法描述、 输入样例、 输出样例,程序代码、 输出结果、时间复杂度分析、优化改进
时间: 2023-07-14 21:14:25 浏览: 57
问题分析:
本题是一个典型的最大权独立集问题,即在一个无向图中选取一些顶点,使得这些顶点两两不相邻,并且这些顶点的权值和最大。
算法描述:
1. 将棋盘中的每个方格看成一个顶点,并将顶点按行列顺序编号,得到一个二维坐标系。
2. 若两个顶点在坐标系中的距离为1,则这两个顶点之间有一条边。
3. 对这个无向图求解最大权独立集问题即可。
输入样例:
3 3
1 2 3
3 2 3
2 3 1
输出样例:
11
程序代码:
相关问题
网络流方格取数问题python: 在一个有m×n个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。 输入:第 1 行有 2 个正整数 m 和 n,分别表示棋盘的行数和列数。接下来的 m 行,每行有 n 个正整数,表示棋盘方格中的数。
以下是一个Python实现:
```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算法求解最大流,即可得到答案。
网络流算法解方格取数问题python: 在一个有m×n个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。 输入:第 1 行有 2 个正整数 m 和 n,分别表示棋盘的行数和列数。接下来的 m 行,每行有 n 个正整数,表示棋盘方格中的数。
以下是Python代码实现:
```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)
```
使用示例:
```python
board = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(max_score(board)) # 输出15
```