#!/usr/bin/python2.7 from pprint import pprint from collections import deque dest, cap, flow = range(3) def bfs(graph): visited = [False] * len(graph) q = deque([[-1]]) while len(q): p = q.popleft() for i in graph[p[-1]]: # for all nodes adjacent to last in path if i[dest] == -2: # check if made it to exit return p + [-2] if visited[i[dest]]: # skip if already visited continue # otherwise add as new path visited[i[dest]] = True q.append(p[:] + [i[dest]]) return None def minpath(graph): path = bfs(graph) if not path: return None, None small = 2000000 for i in range(len(path) - 2): small = min(small, filter(lambda x: x[0] is path[i + 1], graph[path[i]])[0][1]) return path, small def augmenting_path(graph): aug = {i: [] for i in graph.keys()} for node in graph: for edge in graph[node]: if edge[flow] < edge[cap]: aug[node].append([edge[dest], edge[cap] - edge[flow]]) if edge[flow] > 0: aug[edge[dest]].append([node, edge[flow]]) return aug def path_index(edges, n): for i in enumerate(edges): if i[1][dest] == n: return i[0] return None def augment(graph, path, n): for i in range(len(path) - 1): start, end = path[i], path[i + 1] temp = path_index(graph[start], end) if temp is None: # if it was a backwards path temp = path_index(graph[end], start) graph[end][temp][flow] -= n else: graph[start][temp][flow] += n def answer(entrances, exits, path): capflow = {} # use -1 as sentinal for entrances (-2 will be exit) capflow[-1] = [[i, 2000000, 0] for i in entrances] capflow[-2] = [] for i in range(len(path)): if i in exits: capflow[i] = [[-2, 2000000, 0]] else: capflow[i] = [ [j, path[i][j], 0] for j in range(len(path[i])) if path[i][j] != 0 ] while True: # pprint(capflow) aug = augmenting_path(capflow) # pprint(aug) path, n = minpath(aug) # pprint(path) if not path: break if augment(capflow, path, n): break return sum(capflow[i][0][flow] for i in exits) entrances = [0, 1] exits = [4, 5] path = [ [0, 3, 7, 0, 0, 0], [3, 0, 0, 2, 0, 0], [0, 0, 0, 2, 1, 0], [0, 0, 3, 0, 0, 4], [1, 0, 2, 2, 0, 0], [0, 1, 2, 2, 0, 0], ] # entrances = [0] # exits = [3] # path = [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]] # 6 # entrances = [0, 1] # exits = [4, 5] # path = [ # [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 print answer(entrances, exits, path)