Вы взорвали устройство Lambchop Summerday и облегчили кроликов их рабочих дураков – и теперь вам нужно сбежать с космической станции как можно быстрее и как можно более упорядоченным! Все кролики собрались в различных местах по всей станции и должны пробиться к, казалось бы, бесконечному количеству спасательных стручков, расположенных в других частях станции. Вам нужно получить многочисленные кролики через различные комнаты в капсулы Escape. К сожалению, коридоры между комнатами могут поместиться только так много кроликов за раз. Более того, многие из коридоров были изменены, чтобы приспособиться к Lambchop, поэтому они различаются в том, сколько кроликов может проходить через них за раз.
Учитывая номера стартовой комнаты групп кроликов, номера комнат для спасения и сколько кроликов может проходить за раз в каждом направлении каждого коридора между ними, выясните, сколько кроликов может безопасно добраться до выхода стручки за раз на пике.
Напишите функциональное решение (входы, выходы, путь), которое требует множества целых чисел, обозначающих то, где находятся группы собравшихся кроликов, множество целых чисел, обозначающих то, где расположены беглые стручки, и множество целых чисел коридоров. Возвращение общего количества кроликов, которые могут проходить на каждом временном шаге как int. Входы и выходы не смешаны и, следовательно, никогда не будут перекрываться. Элемент пути описывает, что коридор, переходящий от A к B, может соответствовать C -кроликам на каждом шаге. Есть не более 50 номеров, соединенных коридорами, и не более 2000000 кроликов, которые подойдут за раз.
Например, если у вас есть: Entranse = [0, 1] Exits = [4, 5] Путь = [[0, 0, 4, 6, 0, 0], # Комната 0: Кролики [0, 0, 5, 2, 0, 0], # Комната 1: кролики [0, 0, 0, 0, 4, 4], # Комната 2: промежуточная комната [0, 0, 0, 0, 6 , 6], # Комната 3: Промежуточная комната [0, 0, 0, 0, 0, 0], # Комната 4: Стокоды побега [0, 0, 0, 0, 0, 0], # Комната 5: ]
Затем на каждом временном этапе может произойти следующее: 0 отправляет 4/4 кролика на 2 и 6/6 кролика на 3 1 отправляет 4/5 кроликов на 2 и 2/2 кролика на 3 2 отправляет 4/4 кролика на 4 и и 4/4 кролика на 5 3 отправляют 4/6 кроликов на 4 и 4/6 кролика на 5
Таким образом, в общей сложности 16 кроликов могли бы добраться до капсула Escape на 4 и 5 на каждом шаге. (Обратите внимание, что в этом примере комната 3 могла бы отправить любые варианты 8 кроликов до 4 и 5, таких как 2/6 и 6/6, но окончательное решение остается прежним.)
Чтобы обеспечить решение Java, редактировать Solution.java Чтобы обеспечить решение Python, редактировать Solution.py
Ваш код должен пройти следующие тестовые примеры. Обратите внимание, что он также может быть запущен против скрытых тестовых случаев, не показанных здесь.
Ввод: Solution.Solution ([0], [3], [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]]) Вывод: 6
Ввод: Solution.Solution ([0, 1], [4, 5], [[0, 0, 4, 6, 0, 0], [0, 0, 5, 2, 0, 0], [0, 0, 0, 0, 4, 4], [0, 0, 0, 0, 6, 6], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]) Вывод: 16
from collections import deque
CORRIDOR_CAPACITY = 2000001
# Great ref: https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
class EscapePods:
def __init__(self, entrances, exits, path):
n = len(path)
m = n + 2
# graph[0] is the new single source s
# graph[-1] is the new single sink t
self.graph = []
self.size = m
for i in range(m):
self.graph.append([0] * m)
for i in range(n):
for j in range(n):
self.graph[i+1][j+1] = path[i][j]
for num in entrances:
self.graph[0][num + 1] = CORRIDOR_CAPACITY
for num in exits:
self.graph[num + 1][m - 1] = CORRIDOR_CAPACITY
def bfs(self):
parents = [-1] * self.size
queue = deque()
queue.append(0)
while queue and parents[-1] == -1:
u = queue.popleft()
for v in range(self.size):
if self.graph[u][v] > 0 and parents[v] == -1:
queue.append(v)
parents[v] = u
path = []
u = parents[-1]
while u != 0:
if u == -1:
return None
path.append(u)
u = parents[u]
path.reverse()
return path
def solve(self):
max_flow = 0
path = self.bfs()
while path:
cap = CORRIDOR_CAPACITY
u = 0
for v in path:
cap = min(cap, self.graph[u][v])
u = v
max_flow += cap
u = 0
for v in path:
self.graph[u][v] -= cap
self.graph[v][u] += cap
u = v
path = self.bfs()
return max_flow
def solution(entrances, exits, path):
escape_pods = EscapePods(entrances, exits, path)
res = escape_pods.solve()
return res
Оригинал: “https://dev.to/itepsilon/foobar-escape-pods-2ema”