Hi,
I'm trying to write a code in python that takes an array of integers as
sources, an array of integers as sinks, and an array of an array of
integers of capacities, returning the maximum flow. I'm new to python and I
got memory error, can you plaese help me because i have no idea how to
solve this problem?
entrances: sources
exits: sinks
path: capacities
------------------------------------------------------------------------------------------------------------------
def answer(entrances, exits, path):
maxflow = 0
for i in exits:
path[i] = [0] * len(path)
for i in range(len(path)):
for j in entrances:
path[i][j] = 0
for i in entrances:
augpathgen = bfs_paths(path, i, exits)
while True:
try:
augpath = next(augpathgen)
except StopIteration:
break
flows = [path[augpath[j]][augpath[j+1]] for j in
range(len(augpath)-1)]
minCap = min(flows)
maxflow += minCap
for j in range(len(augpath)-1):
path[augpath[j]][augpath[j+1]] -= minCap
return maxflow
def bfs_paths(graph, start, goal):
queue = [(start, [start])]
while queue:
(vertex, path) = queue.pop(0)
for next in range(len(graph[vertex])):
if graph[vertex][next] != 0:
if next in goal:
yield path + [next]
elif next not in path:
queue.append((next, path + [next]))
--------------------------------------------------------------------------------------------------------------------
thanks a lot
El
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
