我试图在这篇博客文章中研究谷歌foobar问题。(问题如下所述。(
作者在博客中发布了他的代码，并声称它是由Dinic的算法解决的。
我在相关的维基百科页面上阅读了Dinic的算法，并观看了YouTube视频。我发现代码(附在下面(记录得很糟糕，我不知道算法是如何在代码中实现的。特别是，我看不出"；电平图"；以及"；"阻塞流"；建造。
有人能看到函数bfs()中的while大循环在做什么吗？
给定各组兔子的起始房间编号、逃生舱的房间编号，以及在其间每条走廊的每个方向上一次可以容纳多少只兔子，计算出在高峰期一次可以安全到达逃生舱的兔子数量。
编写一个函数答案(入口、出口、路径(，它采用一个整数数组来表示聚集的兔子群在哪里，一个整数阵列来表示逃生舱所在的位置，以及一个走廊整数数组来返回在每个时间步长可以通过的兔子总数作为int。入口和出口是不相交的，因此永远不会重叠。路径元素path[A][B]=C描述了从A到B的走廊在每个时间步长都可以容纳C只兔子。走廊最多可连接50个房间，一次最多可容纳2000000只兔子。
例如，如果您有：
entrances = [0, 1]
exits = [4, 5]
path = [ [0, 0, 4, 6, 0, 0], # Room 0: Bunnies
[0, 0, 5, 2, 0, 0], # Room 1: Bunnies
[0, 0, 0, 0, 4, 4], # Room 2: Intermediate room
[0, 0, 0, 0, 6, 6], # Room 3: Intermediate room
[0, 0, 0, 0, 0, 0], # Room 4: Escape pods
[0, 0, 0, 0, 0, 0], # Room 5: Escape pods ]
然后在每个时间步骤中，可能会发生以下情况：
0 sends 4/4 bunnies to 2 and 6/6 bunnies to 3
1 sends 4/5 bunnies to 2 and 2/2 bunnies to 3
2 sends 4/4 bunnies to 4 and 4/4 bunnies to 5
3 sends 4/6 bunnies to 4 and 4/6 bunnies to 5
因此，总共有16只兔子可以在每个时间步长的4点和5点到达逃生舱。(请注意，在这个例子中，3号房间本可以将8只兔子的任何变体发送给4只和5只，例如2/6和6/6，但最终答案保持不变。(
def bfs(matrix, source, destination):
visited = [-1 for i in range(len(matrix))]
visited[source] = source
queue = [source]
while len(queue) > 0:
top = queue.pop(0)
for i in range(len(matrix)):
if (matrix[top][i][1] - matrix[top][i][0]) != 0 and visited[i] == -1:
if i == destination:
# Get route
visited[destination] = top
path = [destination]
temp = destination
while temp != source:
temp = visited[temp]
path.append(temp)
path.reverse()
# Get flow value and update augmented graph
temp = 1
total = float("inf")
cur = source
while temp != len(path):
entry = matrix[cur][path[temp]]
diff = abs(entry[1]) - entry[0]
total = min(total, diff)
cur = path[temp]
temp += 1
temp = 1
cur = source
while temp != len(path):
entry = matrix[cur][path[temp]]
if entry[1] < 0: # Already augmented need to flip
entry[1] += total
else:
entry[0] += total
entry = matrix[path[temp]][cur]
if entry[1] <= 0: # Already augmented need to flip
entry[1] -= total
else:
entry[0] += total
cur = path[temp]
temp += 1
return True
else:
visited[i] = top
queue.append(i)
return False
def answer(entrances, exits, path):
max_val = sum(list(map(sum, path)))
aug = []
for i in range(len(path)):
aug.append([])
for j in range(len(path[i])):
aug[i].append([0, path[i][j]])
aug[i].append([0, 0])
if i in exits:
aug[i].append([0, max_val])
else:
aug[i].append([0, 0])
aug.append([])
aug.append([])
for i in range(len(path[0]) + 2):
if i in entrances:
aug[-2].append([0, max_val])
else:
aug[-2].append([0, 0])
aug[-1].append([0, 0])
while bfs(aug, len(aug)-2, len(aug)-1):
pass
total = 0
for i in range(len(aug)):
total += aug[-2][i][0]
return total
作者搞错了。这段代码实现了Edmonds–Karp(专门针对Ford–Fulkerson，所以turtle的评论是正确的(，它反复扩充残差网络中的最短路径。