1、深度优先遍历（DFS）-- （463. 岛屿的周长）
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
def dfs(i, j):
if not 0 <= i < len(grid): return 1
if not 0 <= j < len(grid[i]): return 1
if grid[i][j] == 2: return 0
if grid[i][j] == 0: return 1
grid[i][j] = 2
return dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j - 1) + dfs(i, j + 1)
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == 1:
return dfs(i,j)
return 0也可以使用栈的形式进行遍历， 类似于2
进阶：子树序列化哈希 -- 删除系统中的重复文件夹
class Tree:
def __init__(self, val):
self.child = {}
self.val = val
self.is_del = 0
def add(self, c):
if c not in self.child:
self.child[c] = Tree(c)
return self.child[c]
class Solution:
def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:
root = Tree("/")
mp = defaultdict(list)
s = set()
for path in paths:
p = root
for c in path:
p = p.add(c)
def dfs_pattern(p):
arr = []
for np in sorted(p.child.keys()):
arr.append(dfs_pattern(p.child[np]))
if len(arr) > 0:
res = f"[{','.join(arr)}]"
mp[res].append(p)
return p.val + res
return p.val
dfs_pattern(root)
for pattern in mp:
if len(mp[pattern]) > 1:
for p in mp[pattern]:
p.is_del = 1
res = []
def dfs(p, path):
if len(path) > 0:
res.append(path)
for np in p.child:
if p.child[np].is_del == 0:
dfs(p.child[np], path + [np])
dfs(root, [])
return res2、广度优先遍历（BFS） -- （1254. 统计封闭岛屿的数目）
class Solution:
def closedIsland(self, grid: List[List[int]]) -> int:
v, res = set(), 0
m, n = len(grid), len(grid[0])
for i, j in product(range(m), range(n)):
if (i, j) not in v and grid[i][j] == 0:
flag = True
q = deque([(i, j)])
v.add((i, j))
while q:
i, j = q.popleft()
for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
if not 0 <= ni < m or not 0 <= nj < n:
flag = False
continue
if grid[ni][nj] == 1: continue
if (ni, nj) in v: continue
q.append((ni, nj))
v.add((ni, nj))
if flag: res += 1
return res（1）技巧一：根据障碍物围城最大面积排除 -- 逃离大迷宫
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
q = deque([(0, 0, 0, k)])
v = set([(0, 0, k)])
while q:
s, i, j, k = q.popleft()
if (i, j) == (m - 1, n - 1): return s
for ni, nj in (i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1):
if not (0 <= ni < m and 0 <= nj < n): continue
if grid[ni][nj] == 1 and k >= 1:
if (ni, nj, k - 1) in v: continue
v.add((ni, nj, k - 1))
q.append((s + 1, ni, nj, k - 1))
elif grid[ni][nj] == 0:
if (ni, nj, k) in v: continue
v.add((ni, nj, k))
q.append((s + 1, ni, nj, k))
return -1（2）技巧二：根据已经排除障碍数设置相应的状态 -- 网格中的最短路径
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
q = deque([(0, 0, 0, k)])
v = set([(0, 0, k)])
while q:
s, i, j, k = q.popleft()
if (i, j) == (m - 1, n - 1): return s
for ni, nj in (i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1):
if not (0 <= ni < m and 0 <= nj < n): continue
if grid[ni][nj] == 1 and k >= 1:
if (ni, nj, k - 1) in v: continue
v.add((ni, nj, k - 1))
q.append((s + 1, ni, nj, k - 1))
elif grid[ni][nj] == 0:
if (ni, nj, k) in v: continue
v.add((ni, nj, k))
q.append((s + 1, ni, nj, k))
return -1（3）技巧三：使用双向BFS -- 单词接龙
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
notVisited = set(wordList)
if endWord not in notVisited: return 0
def getNeighbors(word):
res = []
for i in range(len(word)):
for j in string.ascii_letters[0:26]:
if word[i] != j:
res.append(word[:i] + j + word[i + 1:])
return res
q1 = set([beginWord])
q2 = set([endWord])
l = 2
while q1 and q2:
if len(q1) > len(q2):
q1, q2 = q2, q1
q3 = set()
for w in q1:
nws = getNeighbors(w)
for nw in nws:
if nw in q2:
return l
if nw in notVisited:
notVisited.remove(nw)
q3.add(nw)
q1 = q3
l += 1
return 03、0-1BFS -- （2290. 到达角落需要移除障碍物的最小数目）
class Solution:
def minimumObstacles(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dis = [[inf] * n for _ in range(m)]
dis[0][0], q = 0, deque([(0, 0)])
while q:
i, j = q.popleft()
for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
if not 0 <= ni < m: continue
if not 0 <= nj < n: continue
g = grid[ni][nj]
if dis[i][j] + g < dis[ni][nj]:
dis[ni][nj] = dis[i][j] + g
if g == 0: q.appendleft((ni, nj))
else: q.append((ni, nj))
return dis[-1][-1]4、最短路径算法-迪杰斯特拉(Dijkstra)算法 （使用堆）-- （1514. 概率最大的路径）
class Solution:
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
m = defaultdict(list)
for i, edge in enumerate(edges):
m[edge[0]].append((edge[1], succProb[i]))
m[edge[1]].append((edge[0], succProb[i]))
q = []
heappush(q, (-1, start))
v = set()
while q:
p, i = heappop(q)
if i == end: return -p
if i in v: continue
v.add(i)
for j, np in m[i]:
if j not in v:
heappush(q, (p * np, j))
return 0小技巧：加入虚拟原点，例如 购买苹果的最低成本 ，到每个点的距离为appleCost[i]，那么就可以将每个点到其他点的最短路 转化为 虚拟原点到其他点的最短路
class Solution:
def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:
dist, start = [inf] * (n + 1), n
dist[start] = 0
m = defaultdict(list)
for f, t, w in roads:
f, t = f - 1, t - 1
m[f].append((t, w * (k + 1)))
m[t].append((f, w * (k + 1)))
for i in range(n):
m[start].append((i, appleCost[i]))
m[i].append((start, appleCost[i]))
hq = [(0, start)]
while hq:
curDist, p = heappop(hq)
if dist[p] < curDist:
continue
for np, w in m[p]:
cand = dist[p] + w
if cand < dist[np]:
dist[np] = cand
heappush(hq, (dist[np], np))
return dist[:-1]对于多源最短路问题，可以使用Floyd算法，例如 -- 转换字符串的最小成本 I
class Solution:
def minimumCost(self, src: str, tag: str, ori: List[str], dst: List[str], c: List[int]) -> int:
nn = len(ori)
m = defaultdict(lambda: inf)
for i in range(nn):
f, t = ord(ori[i]) - ord('a'), ord(dst[i]) - ord('a')
if c[i] < m[f, t]:
m[f, t] = c[i]
n = len(src)
d = [[inf] * 26 for _ in range(26)]
for i in range(26):
d[i][i] = 0
for j in range(26):
if i != j:
d[i][j] = m[i, j]
for k in range(26):
for i in range(26):
for j in range(26):
if d[i][k]+ d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
res = 0
for i in range(n):
f, t = ord(src[i]) - ord('a'), ord(tag[i]) - ord('a')
if d[f][t] == inf:
return -1
res += d[f][t]
return res另外：广度优先算法是一种特殊的最短路径算法，按照出入队列次数进行排序，例如 -- 跳跃游戏 IV
class Solution:
def minJumps(self, arr: List[int]) -> int:
q = deque([(0, 0)])
m = defaultdict(list)
s = [0] + [inf] * (len(arr) - 1)
for i, a in enumerate(arr):
m[a].append(i)
while q:
i, p = q.popleft()
if i == len(arr) - 1: return p
for j in m[arr[i]]:
if i == j: continue
if p + 1 >= s[j]: continue
s[j] = p + 1
q.append((j, p + 1))
m[arr[i]] = []
if i + 1 < len(arr) and p + 1 < s[i + 1]:
s[i + 1] = p + 1
q.append((i + 1, p + 1))
if i - 1 >= 0 and p + 1 < s[i - 1]:
s[i - 1] = p + 1
q.append((i - 1, p + 1))
return -1可以通过记录每个点的最短路径来去重 -- 到达目的地的第二短时间
class Solution:
def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
q = deque([(1, 0)])
m = defaultdict(list)
for f, t in edges:
m[f].append(t)
m[t].append(f)
minl, l = inf, inf
dist = [[inf] * 2 for _ in range(n + 1)]
dist[1][0] = 0
while dist[n][1] == inf:
p, s = q.popleft()
for np in m[p]:
if s + 1 < dist[np][0]:
dist[np][0] = s + 1
q.append((np, s + 1))
elif dist[np][0] < s + 1 < dist[np][1]:
dist[np][1] = s + 1
q.append((np, s + 1))
t = 0
for _ in range(dist[n][1]):
if (t // change) % 2 == 0:
t += time
else:
t = t // change * change + change + time
return t5、并查集 -- （684. 冗余连接）
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
res = []
parent = {}
def find(i):
if parent.get(i, i) != i:
parent[i] = find(parent[i])
return parent.get(i, i)
def union(i, j):
parent[find(i)] = find(j)
for edge in edges:
if find(edge[0]) == find(edge[1]):
return edge
else:
union(edge[0], edge[1])
return res可以对并查集加入数量统计和长度统计，例如：检查边长度限制的路径是否存在 II
class DistanceLimitedPathsExist:
def __init__(self, n: int, edgeList: List[List[int]]):
self.f = list(range(n))
self.size = [1] * n
self.cost = [0] * n
for u, v, w in sorted(edgeList, key=lambda x: x[-1]):
self.union(u, v, w)
def find(self, x, limit):
while self.f[x] != x and self.cost[x]<limit:
x = self.f[x]
return x
def union(self, x, y, w):
fx, fy = self.find(x, w+1), self.find(y, w+1)
if fx == fy:
return
if self.size[fx]>self.size[fy]:
fx, fy = fy, fx
self.f[fx] = fy
self.size[fy] += self.size[fx]
self.cost[fx] = w
def query(self, p: int, q: int, limit: int) -> bool:
return self.find(p, limit) == self.find(q, limit)6、拓扑排序 -- （207. 课程表）
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
edges = collections.defaultdict(list)
indeg = [0] * numCourses
for info in prerequisites:
edges[info[1]].append(info[0])
indeg[info[0]] += 1
q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])
visited = 0
while q:
visited += 1
u = q.popleft()
for v in edges[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return visited == numCourses无向图（树）也可以进行拓扑排序，实现从叶子节点到根节点的遍历 -- 可以被 K 整除连通块的最大数目
class Solution:
def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:
m = defaultdict(list)
mt = defaultdict(int)
for f, t in edges:
m[f].append(t)
m[t].append(f)
mt[t] += 1
mt[f] += 1
q = deque()
for p in range(n):
if len(m[p]) <= 1:
q.append(p)
mt[p] = 0
h = n * [0]
res = 0
while q:
p = q.popleft()
if (values[p] + h[p]) % k == 0:
res += 1
values[p] = h[p] = 0
for np in m[p]:
if mt[np] <= 0: continue
h[np] += values[p] + h[p]
mt[np] -= 1
if mt[np] == 1:
q.append(np)
mt[p] = 0
return res进阶版 -- 组间拓扑排序 -- 项目管理
class Solution:
def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
mg_in = defaultdict(int)
mg = defaultdict(set)
m_in = defaultdict(int)
mm = defaultdict(lambda:defaultdict(list))
for i, be in enumerate(beforeItems):
for b in be:
mm[group[b]][b].append(i)
m_in[i] += 1
if group[b] != -1 and group[i] != -1 and group[i] != group[b]:
mg[group[b]].add(group[i])
if group[i] > -1 and group[i] != group[b]:
mg_in[group[i]] += 1
res = []
qg = deque()
q = defaultdict(deque)
for i in range(-1, m):
if i > -1: mg[-1].add(i)
if mg_in[i] == 0:
qg.append(i)
for i in range(n):
if m_in[i] == 0:
q[group[i]].append(i)
while qg:
g = qg.popleft()
def f(g):
while q[g]:
i = q[g].popleft()
res.append(i)
for j in mm[g][i]:
m_in[j] -= 1
if group[j] != group[i]:
mg_in[group[j]] -= 1
if m_in[j] == 0:
q[group[j]].append(j)
f(-1);f(g)
for ng in mg[g]:
if mg_in[ng] == 0:
qg.append(ng)
else: f(-1)
if len(res) < n: return []
return res7、欧拉回路 -- Hierholzer算法 -- （332. 重新安排行程）
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
def dfs(curr: str):
while vec[curr]:
tmp = heapq.heappop(vec[curr])
dfs(tmp)
stack.append(curr)
vec = collections.defaultdict(list)
for depart, arrive in tickets:
vec[depart].append(arrive)
for key in vec:
heapq.heapify(vec[key])
stack = list()
dfs("JFK")
return stack[::-1]8、最小生成树
（1）kruskal （基于边的算法，并查集 + 排序） -- （连接所有点的最小费用）
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
parent = {}
def find(a):
if parent.get(a, a) != a:
parent[a] = find(parent[a])
return parent.get(a, a)
def union(a, b):
parent[find(a)] = find(b)
get_dis = lambda x, y:abs(x[0] - y[0]) + abs(x[1] - y[1])
dis_arr = []
for i, x in enumerate(points):
for j in range(i + 1, len(points)):
y = points[j]
dis_arr.append((get_dis(x, y), i, j))
dis_arr.sort()
res, n = 0, 0
for dis, i, j in dis_arr:
if find(i) != find(j):
res += dis
n += 1
if n == len(points) - 1:
return res
union(i, j)
return res（2）Prim算法 （基于顶点） -- （连接所有点的最小费用）
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
res, n = 0, len(points)
minHeap = []
MST = set()
heapq.heappush(minHeap, (0, tuple(points[0])))
while minHeap and len(MST) < n:
cost, x = heapq.heappop(minHeap)
if x in MST:
continue
MST.add(x)
res += cost
for y in points:
if tuple(y) not in MST:
heapq.heappush(minHeap, (abs(x[0] - y[0]) + abs(x[1] - y[1]), tuple(y)))
return res9、连通性问题 -- tarjan算法， 找割边 -- （1192. 查找集群内的关键连接）
class Solution:
def criticalConnections(self, n, connections):
ans, low, d = [], [-1] * n, [[] for _ in range(n)]
for i, j in connections:
d[i].append(j)
d[j].append(i)
def tarjan(c, v, p):
dfn = low[v] = c
for i in d[v]:
if i != p:
if low[i] == -1:
c += 1
tarjan(c, i, v)
if low[i] > dfn:
ans.append([v, i])
low[v] = min(low[v], low[i])
tarjan(0, 0, -1)
return ans找割点 -- 使陆地分离的最少天数
class Solution:
def minDays(self, grid: List[List[int]]) -> int:
parent = {}
def find(i):
if parent.get(i, i) != i:
parent[i] = find(parent[i])
return parent.get(i, i)
def union(i, j):
parent[find(i)] = find(j)
low, d = defaultdict(lambda: 0), defaultdict(list)
dfn = defaultdict(int)
def tarjan(u, parent=None, tick=1): # 找割点的数量
dfn[u] = low[u] = tick
child_cnt = 0 # 联通子树数量
for v in d[u]:
if dfn[v] == 0: # 未被访问过
if tarjan(v, u, tick + 1): # 找到一个割点就返回
return True
low[u] = min(low[u], low[v])
child_cnt += 1
# 判断割点
q1 = parent is None and child_cnt >= 2 # 根节点至少有两个儿子时，根节点u是割点
q2 = parent and low[v] >= dfn[u] # 非根节点，此时u是割点
if q1 or q2:
return True
elif v != parent: # 已访问过
low[u] = min(low[u], dfn[v])
return False
m, n = len(grid), len(grid[0])
for i, j in product(range(m), range(n)):
if grid[i][j] == 1:
if i + 1 < m and grid[i + 1][j] == 1:
d[i, j].append((i + 1, j))
d[i + 1, j].append((i, j))
union((i, j), (i + 1, j))
if j + 1 < n and grid[i][j + 1] == 1:
union((i, j), (i, j + 1))
d[i, j].append((i, j + 1))
d[i, j + 1].append((i, j))
s, t = set(), 0
for i, j in product(range(m), range(n)):
if grid[i][j] == 1:
s.add(find((i, j)))
t += 1
if len(s) == 0 or len(s) >= 2:
return 0
if t == 1: return 1
for i, j in product(range(m), range(n)):
if grid[i][j] == 1:
if tarjan((i, j)):
return 1
return 210、匈牙利算法 -- 处理二分图 （最多邀请的个数）
class Solution:
def maximumInvitations(self, grid: List[List[int]]) -> int:
boy, girl = len(grid), len(grid[0])
link = [-1] * girl
vis = set()
# 二分图匹配
def hungary():
cnt = 0
for u in range(boy):
vis.clear()
cnt += dfs(u)
return cnt
def dfs(u):
for v in range(girl):
if grid[u][v] and v not in vis:
vis.add(v)
if link[v] == -1 or dfs(link[v]):
link[v] = u
return 1
return 0
return hungary()import numpy as np
from scipy.optimize import linear_sum_assignment
class Solution:
def minimumMoves(self, grid: List[List[int]]) -> int:
l0=[] ##没有石头的位置
lm=[] ##多余石头的位置
for r in range(3):
for c in range(3):
if grid[r][c]==0:
l0.append([r,c])
if grid[r][c]>1:
for t in range(grid[r][c]-1):
lm.append([r,c])
n=len(l0) ##表示有 n个匹配问题
matrix=[[0]*n for _ in range(n)]
def dist(p1,p2):
x1,y1=p1
x2,y2=p2
return abs(x1-x2)+abs(y1-y2)
for i in range(n):
for j in range(n):
matrix[i][j]=dist(lm[i],l0[j])
matrix=np.array(matrix) ##np数据
row_indices, col_indices = linear_sum_assignment(matrix)
# 计算最小结果
min_result = matrix[row_indices, col_indices].sum()
# print(min_result,type(min_result)) ##类型是np.int64 因为使用了numpy数据包
return int(min_result)11、启发式搜索（A*算法）-- 滑动谜题
class AStar:
DIST = [
[0, 1, 2, 1, 2, 3],
[1, 0, 1, 2, 1, 2],
[2, 1, 0, 3, 2, 1],
[1, 2, 3, 0, 1, 2],
[2, 1, 2, 1, 0, 1],
[3, 2, 1, 2, 1, 0],
]
# 计算启发函数
@staticmethod
def getH(status: str) -> int:
ret = 0
for i in range(6):
if status[i] != "0":
ret += AStar.DIST[i][int(status[i]) - 1]
return ret
def __init__(self, status: str, g: str) -> None:
self.status = status
self.g = g
self.h = AStar.getH(status)
self.f = self.g + self.h
def __lt__(self, other: "AStar") -> bool:
return self.f < other.f
class Solution:
NEIGHBORS = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
def slidingPuzzle(self, board: List[List[int]]) -> int:
# 枚举 status 通过一次交换操作得到的状态
def get(status: str) -> Generator[str, None, None]:
s = list(status)
x = s.index("0")
for y in Solution.NEIGHBORS[x]:
s[x], s[y] = s[y], s[x]
yield "".join(s)
s[x], s[y] = s[y], s[x]
initial = "".join(str(num) for num in sum(board, []))
if initial == "123450":
return 0
q = [AStar(initial, 0)]
seen = {initial}
while q:
node = heapq.heappop(q)
for next_status in get(node.status):
if next_status not in seen:
if next_status == "123450":
return node.g + 1
heapq.heappush(q, AStar(next_status, node.g + 1))
seen.add(next_status)
return -112、最小费用最大流问题 -- 将石头分散到网格图的最少移动次数
最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求。
在实际中：n辆卡车要运送物品，从A地到B地。由于每条路段都有不同的路费要缴纳，每条路能容纳的车的数量有限制，如何分配卡车的出发路径可以达到费用最低，物品又能全部送到。
# 最小费用最大流板子
from heapq import heappop, heappush
class Csr():
def __init__(self, n: int, edges: list):
self.start = [0] * (n + 1)
self.elist = [0] * len(edges)
for e in edges:
self.start[e[0] + 1] += 1
for i in range(1, n + 1):
self.start[i] += self.start[i - 1]
counter = self.start[::]
for e in edges:
self.elist[counter[e[0]]] = e[1]
counter[e[0]] += 1
class MinCostFlow:
_INF = 9_223_372_036_854_775_807
def __init__(self, n=0):
self._n = n
self._edges = [] # [from_, to, cap, flow, cost]
self._log_max_n = 30
self._bitmask = (1 << self._log_max_n) - 1
def add_edge(self, from_, to, cap, cost):
assert 0 <= from_ < self._n
assert 0 <= to < self._n
assert 0 <= cap
assert 0 <= cost
m = len(self._edges)
self._edges.append([from_, to, cap, 0, cost])
return m
def get_edge(self, i):
m = len(self._edges)
assert 0 <= i < m
return self._edges[i]
def edges(self):
return self._edges
def flow(self, s, t, flow_limit=_INF):
return self.slope(s, t, flow_limit)[-1]
def slope(self, s, t, flow_limit=_INF):
assert 0 <= s < self._n
assert 0 <= t < self._n
assert s != t
m = len(self._edges)
edge_idx = [0] * m
degree = [0] * self._n
redge_idx = [0] * m
elist = [] # [e_num, edge=[to, rev, cap, cost]]
for i in range(m):
from_, to, cap, flow, cost = self._edges[i]
edge_idx[i] = degree[from_]
degree[from_] += 1
redge_idx[i] = degree[to]
degree[to] += 1
elist.append([from_, [to, -1, cap - flow, cost]])
elist.append([to, [from_, -1, flow, -cost]])
g = Csr(self._n, elist)
for i in range(m):
from_, to, cap, flow, cost = self._edges[i]
edge_idx[i] += g.start[from_]
redge_idx[i] += g.start[to]
g.elist[edge_idx[i]][1] = redge_idx[i]
g.elist[redge_idx[i]][1] = edge_idx[i]
result = self._slope(g, s, t, flow_limit)
for i in range(m):
cap = g.elist[edge_idx[i]][2]
self._edges[i][3] = self._edges[i][2] - cap
return result
def _slope(self, g, s, t, flow_limit):
dual_dist = [[0, 0] for _ in range(self._n)]
prev_e = [0] * self._n
def dual_ref():
for i in range(self._n):
dual_dist[i][1] = MinCostFlow._INF
vis = [False] * self._n
que_min = []
que = [] # heapq
# heap_r = 0
dual_dist[s][1] = 0
que_min.append(s)
while que_min or que:
v = 0
if que_min:
v = que_min.pop()
else:
v = heappop(que) & self._bitmask
if vis[v]:
continue
vis[v] = True
if v == t:
break
dual_v, dist_v = dual_dist[v]
for i in range(g.start[v], g.start[v+1]):
to, rev, cap, cost_i = g.elist[i]
if cap <= 0:
continue
cost = cost_i - dual_dist[to][0] + dual_v
if dual_dist[to][1] - dist_v > cost:
dist_to = dist_v + cost
dual_dist[to][1] = dist_to
prev_e[to] = rev
if dist_to == dist_v:
que_min.append(to)
else:
heappush(que, (dist_to << self._log_max_n) + to)
if not vis[t]:
return False
for v in range(self._n):
if not vis[v]:
continue
dual_dist[v][0] -= dual_dist[t][1] - dual_dist[v][1]
return True
flow = 0
cost = 0
prev_cost_per_flow = -1
result = [[0, 0]]
while flow < flow_limit:
if not dual_ref():
break
c = flow_limit - flow
v = t
while v != s:
to, rev = g.elist[prev_e[v]][:2]
c = min(c, g.elist[rev][2])
v = to
v = t
while v != s:
to, rev = g.elist[prev_e[v]][:2]
g.elist[prev_e[v]][2] += c
g.elist[rev][2] -= c
v = to
d = - dual_dist[s][0]
flow += c
cost += c * d
if prev_cost_per_flow == d:
result.pop()
result.append([flow, cost])
prev_cost_per_flow = d
return result解决方法：
class Solution:
def minimumMoves(self, grid: List[List[int]]) -> int:
non_stone = []
move = []
for i in range(3):
for j in range(3):
for _ in range(1,grid[i][j]):
move.append([i,j])
if grid[i][j] == 0:
non_stone.append([i,j])
n = len(non_stone)
start = 0
end = 2 * n + 1
dinic = MinCostFlow(2*n+2)
for i in range(n):
dinic.add_edge(start,i+1,1,0)
dinic.add_edge(i+1+n,end,1,0)
for i in range(n):
for j in range(n):
dis = abs(non_stone[i][0]-move[j][0]) + abs(non_stone[i][1]-move[j][1])
dinic.add_edge(i+1,j+1+n,1,dis)
return dinic.flow(start,end)[1]13、模拟退火算法 -- 将石头分散到网格图的最少移动次数
import random
import math
class Solution:
def __init__(self) -> None:
random.seed(2023)
self.ans = float('inf')
def minimumMoves(self, grid) -> int:
z = []
g = []
for i in range(3):
for j in range(3):
if grid[i][j] == 0:
z.append((i, j))
while grid[i][j] > 1:
g.append((i, j))
grid[i][j] -= 1
for _ in range(3): # 可以继续调参往低走
self.sa(z, g, 1000, 0.9, 1e-4) # 继续初始温度越低也可以
return self.ans
def energy(self, z, g):
e = 0
for i in range(len(z)):
e += (abs(z[i][0]-g[i][0]) + (abs(z[i][1]-g[i][1])))
self.ans = min(self.ans, e)
return e
def sa(self, z, g, T, fa, low):
while T > low:
T *= fa
e1 = self.energy(z, g)
n = len(z)
if n == 1:
break
while True:
a = random.randint(0, n-1)
b = random.randint(0, n-1)
if a != b:
break
z[a], z[b] = z[b], z[a]
e2 = self.energy(z, g)
dt = e2 - e1
if dt >= 0 and math.exp(-dt/T) > random.random():
z[a], z[b] = z[b], z[a]参考资料：