图论基本算法

1、深度优先遍历（DFS）-- （463. 岛屿的周长）

class Solution:def islandPerimeter(self, grid: List[List[int]]) -> int:def dfs(i, j):if not 0 <= i < len(grid): return 1if not 0 <= j < len(grid[i]): return 1if grid[i][j] == 2: return 0if grid[i][j] == 0: return 1grid[i][j] = 2return 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 = valself.is_del = 0def 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 = rootfor 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 + resreturn p.valdfs_pattern(root)for pattern in mp:if len(mp[pattern]) > 1:for p in mp[pattern]:p.is_del = 1res = []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 res

2、广度优先遍历（BFS） -- （1254. 统计封闭岛屿的数目）

class Solution:def closedIsland(self, grid: List[List[int]]) -> int:v, res = set(), 0m, 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 = Trueq = 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 = Falsecontinueif grid[ni][nj] == 1: continueif (ni, nj) in v: continueq.append((ni, nj))v.add((ni, nj))if flag: res += 1return 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 sfor 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: continuev.add((ni, nj, k - 1)) q.append((s + 1, ni, nj, k - 1))elif grid[ni][nj] == 0:if (ni, nj, k) in v: continuev.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 sfor 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: continuev.add((ni, nj, k - 1)) q.append((s + 1, ni, nj, k - 1))elif grid[ni][nj] == 0:if (ni, nj, k) in v: continuev.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 0def 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 resq1 = set([beginWord])q2 = set([endWord])l = 2while q1 and q2:if len(q1) > len(q2):q1, q2 = q2, q1q3 = set()for w in q1:nws = getNeighbors(w)for nw in nws:if nw in q2:return lif nw in notVisited:notVisited.remove(nw)q3.add(nw)q1 = q3l += 1return 0

3、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: continueif not 0 <= nj < n: continueg = grid[ni][nj]if dis[i][j] + g < dis[ni][nj]:dis[ni][nj] = dis[i][j] + gif 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 -pif i in v: continuev.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), ndist[start] = 0m = defaultdict(list)for f, t, w in roads:f, t = f - 1, t - 1m[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:continuefor np, w in m[p]:cand = dist[p] + wif cand < dist[np]:dist[np] = candheappush(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] = 0for 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 = 0for i in range(n):f, t = ord(src[i]) - ord('a'), ord(tag[i]) - ord('a')if d[f][t] == inf:return -1res += 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 pfor j in m[arr[i]]:if i == j: continueif p + 1 >= s[j]: continues[j] = p + 1q.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, infdist = [[inf] * 2 for _ in range(n + 1)]dist[1][0] = 0while dist[n][1] == inf:p, s = q.popleft()for np in m[p]:if s + 1 < dist[np][0]:dist[np][0] = s + 1q.append((np, s + 1))elif dist[np][0] < s + 1 < dist[np][1]:dist[np][1] = s + 1q.append((np, s + 1))t = 0for _ in range(dist[n][1]):if (t // change) % 2 == 0:t += timeelse:t = t // change * change + change + timereturn t

5、并查集 -- （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 edgeelse: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] * nself.cost = [0] * nfor 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 xdef union(self, x, y, w):fx, fy = self.find(x, w+1), self.find(y, w+1)if fx == fy:returnif self.size[fx]>self.size[fy]:fx, fy = fy, fxself.f[fx] = fyself.size[fy] += self.size[fx]self.cost[fx] = wdef 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] * numCoursesfor info in prerequisites:edges[info[1]].append(info[0])indeg[info[0]] += 1q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])visited = 0while q:visited += 1u = q.popleft()for v in edges[u]:indeg[v] -= 1if 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] += 1mt[f] += 1q = deque()for p in range(n):if len(m[p]) <= 1:q.append(p)mt[p] = 0h = n * [0]res = 0while q:p = q.popleft()if (values[p] + h[p]) % k == 0:            res += 1values[p] = h[p] = 0for np in m[p]:if mt[np] <= 0: continueh[np] += values[p] + h[p]mt[np] -= 1if mt[np] == 1:q.append(np)mt[p] = 0return 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] += 1if 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]] += 1res = []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] -= 1if group[j] != group[i]:mg_in[group[j]] -= 1if 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 res

7、欧拉回路 -- 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, 0for dis, i, j in dis_arr:if find(i) != find(j):res += disn += 1if n == len(points) - 1:return resunion(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:continueMST.add(x)res += costfor 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 res

9、连通性问题 --  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] = cfor i in d[v]:if i != p:if low[i] == -1: c += 1tarjan(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] = tickchild_cnt = 0  # 联通子树数量for v in d[u]:if dfn[v] == 0:  # 未被访问过if tarjan(v, u, tick + 1):  # 找到一个割点就返回return Truelow[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 Trueelif v != parent:  # 已访问过low[u] = min(low[u], dfn[v])return Falsem, 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(), 0for i, j in product(range(m), range(n)):if grid[i][j] == 1:s.add(find((i, j)))t += 1if len(s) == 0 or len(s) >= 2:return 0if t == 1: return 1for i, j in product(range(m), range(n)):if grid[i][j] == 1:if tarjan((i, j)):return 1return 2

10、匈牙利算法 -- 处理二分图 （最多邀请的个数）

class Solution:def maximumInvitations(self, grid: List[List[int]]) -> int:boy, girl = len(grid), len(grid[0])link = [-1] * girlvis = set()# 二分图匹配def hungary():cnt = 0for u in range(boy):vis.clear()cnt += dfs(u)return cntdef 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] = ureturn 1return 0return 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=p1x2,y2=p2return 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],]# 计算启发函数@staticmethoddef getH(status: str) -> int:ret = 0for i in range(6):if status[i] != "0":ret += AStar.DIST[i][int(status[i]) - 1]return retdef __init__(self, status: str, g: str) -> None:self.status = statusself.g = gself.h = AStar.getH(status)self.f = self.g + self.hdef __lt__(self, other: "AStar") -> bool:return self.f < other.fclass 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 0q = [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 + 1heapq.heappush(q, AStar(next_status, node.g + 1))seen.add(next_status)return -1

12、最小费用最大流问题 -- 将石头分散到网格图的最少移动次数

　　最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从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] += 1for 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_807def __init__(self, n=0):self._n = nself._edges = []  # [from_, to, cap, flow, cost]self._log_max_n = 30self._bitmask = (1 << self._log_max_n) - 1def add_edge(self, from_, to, cap, cost):assert 0 <= from_ < self._nassert 0 <= to < self._nassert 0 <= capassert 0 <= costm = len(self._edges)self._edges.append([from_, to, cap, 0, cost])return mdef get_edge(self, i):m = len(self._edges)assert 0 <= i < mreturn self._edges[i]def edges(self):return self._edgesdef 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._nassert 0 <= t < self._nassert s != tm = len(self._edges)edge_idx = [0] * mdegree = [0] * self._nredge_idx = [0] * melist = []  # [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_] += 1redge_idx[i] = degree[to]degree[to] += 1elist.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] - capreturn resultdef _slope(self, g, s, t, flow_limit):dual_dist = [[0, 0] for _ in range(self._n)]prev_e = [0] * self._ndef dual_ref():for i in range(self._n):dual_dist[i][1] = MinCostFlow._INFvis = [False] * self._nque_min = []que = []  # heapq# heap_r = 0dual_dist[s][1] = 0que_min.append(s)while que_min or que:v = 0if que_min:v = que_min.pop()else:v = heappop(que) & self._bitmaskif vis[v]:continuevis[v] = Trueif v == t:breakdual_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:continuecost = cost_i - dual_dist[to][0] + dual_vif dual_dist[to][1] - dist_v > cost:dist_to = dist_v + costdual_dist[to][1] = dist_toprev_e[to] = revif dist_to == dist_v:que_min.append(to)else:heappush(que, (dist_to << self._log_max_n) + to)if not vis[t]:return Falsefor v in range(self._n):if not vis[v]:continuedual_dist[v][0] -= dual_dist[t][1] - dual_dist[v][1]return Trueflow = 0cost = 0prev_cost_per_flow = -1result = [[0, 0]]while flow < flow_limit:if not dual_ref():breakc = flow_limit - flowv = twhile v != s:to, rev = g.elist[prev_e[v]][:2]c = min(c, g.elist[rev][2])v = tov = twhile v != s:to, rev = g.elist[prev_e[v]][:2]g.elist[prev_e[v]][2] += cg.elist[rev][2] -= cv = tod = - dual_dist[s][0]flow += ccost += c * dif prev_cost_per_flow == d:result.pop()result.append([flow, cost])prev_cost_per_flow = dreturn 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 = 0end = 2 * n + 1dinic = 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 mathclass 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] -= 1for _ in range(3): # 可以继续调参往低走self.sa(z, g, 1000, 0.9, 1e-4) # 继续初始温度越低也可以return self.ans def energy(self, z, g):e = 0for 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 edef sa(self, z, g, T, fa, low):while T > low:T *= fae1 = self.energy(z, g)n = len(z)if n == 1:breakwhile True:a = random.randint(0, n-1)b = random.randint(0, n-1)if a != b:breakz[a], z[b] = z[b], z[a]e2 = self.energy(z, g) dt = e2 - e1if dt >= 0 and math.exp(-dt/T) > random.random():z[a], z[b] = z[b], z[a]

参考资料：

773. 滑动谜题 - 力扣（LeetCode）