# Untitled

Sep 22nd, 2019
245
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. test = [[0, 19, 5, 11], [4, 0, 18, 0], [13, 9, 0, 1], [3, 13, 14, 0]]
2.
3.
4.
5.
6.
7. from collections import deque
8.
9.
10. def bfs(matrix):
11.     q = deque()
12.     used = [-1] * (len(matrix))
13.     used[0] = True
14.     q.append(0)
15.
16.     while q:
17.         now = q[0]
18.         q.popleft()
19.         for i in range(0, (len(matrix[now]))):
20.             if (matrix[now][i] != 0 and used[i] == -1):
21.                 q.append(i)
22.                 used[i] = now
23.
24.     return used
25.
26.
27. def pathGet(Story):
28.     result = deque()
29.     used = [False] * (len(Story) + 1)
30.     i = 1
31.     while ((i != 0)):
32.         if used[i] == False:
33.             result.appendleft(i)
34.             i = Story[i]
35.             used[i] = True
36.     result.appendleft(0)
37.     return result
38.
39.
40. def FordFukerson(matrix):
41.     c = matrix
42.
43.     path_matrix = bfs(c)
44.     while path_matrix[1] != -1:
45.
46.         i = 1
47.         path = pathGet(path_matrix)
48.
49.         m = c[path[0]][path[1]]
50.
51.         for i in range(0, len(path) - 1):
52.
53.             a = path[i]
54.             b = path[i + 1]
55.             if c[a][b] < m:
56.                 m = c[a][b]
57.
58.         for i in range(0, len(path) - 1):
59.             a = path[i]
60.             b = path[i + 1]
61.
62.             matrix[a][b] -= m
63.             matrix[b][a] += m
64.
65.
66.
67.             c[a][b] += m
68.             c[b][a] -= m
69.         path_matrix = bfs(c)
70.
71.     result = 0
72.     for i in matrix[0]:
73.         result += i
74.
75.     return result
76.
77. print(FordFukerson(test))