/
ksushaksusha
/
Python
Обзор
Документация
Войти
/
ksushaksusha
/
Python
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
networking_flow/minimum_cut.py
66 строк
2 KB
Mark Mayo
clean of unnecessary checks, imports, calls (#7993)
20 ноя 2022, 14:00
Не верифицирован
20 ноя 2022, 14:00
f32d611
Код
Авторство
О чём код?
# Minimum cut on Ford_Fulkerson algorithm. test_graph = [ [0, 16, 13, 0, 0, 0], [0, 0, 10, 12, 0, 0], [0, 4, 0, 0, 14, 0], [0, 0, 9, 0, 0, 20], [0, 0, 0, 7, 0, 4], [0, 0, 0, 0, 0, 0], ] def bfs(graph, s, t, parent): # Return True if there is node that has not iterated. visited = [False] * len(graph) queue = [s] visited[s] = True while queue: u = queue.pop(0) for ind in range(len(graph[u])): if visited[ind] is False and graph[u][ind] > 0: queue.append(ind) visited[ind] = True parent[ind] = u return visited[t] def mincut(graph, source, sink): """This array is filled by BFS and to store path >>> mincut(test_graph, source=0, sink=5) [(1, 3), (4, 3), (4, 5)] """ parent = [-1] * (len(graph)) max_flow = 0 res = [] temp = [i[:] for i in graph] # Record original cut, copy. while bfs(graph, source, sink, parent): path_flow = float("Inf") s = sink while s != source: # Find the minimum value in select path path_flow = min(path_flow, graph[parent[s]][s]) s = parent[s] max_flow += path_flow v = sink while v != source: u = parent[v] graph[u][v] -= path_flow graph[v][u] += path_flow v = parent[v] for i in range(len(graph)): for j in range(len(graph[0])): if graph[i][j] == 0 and temp[i][j] > 0: res.append((i, j)) return res if __name__ == "__main__": print(mincut(test_graph, source=0, sink=5))