Advertisement
HellFinger

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))
Advertisement
RAW Paste Data Copied
Advertisement