pastebin

Paste Search Dynamic
Recent pastes
find path
  1. def find_path(s, t, graph, path=[]):
  2.        
  3.         new_path = path.copy()
  4.         new_path.append(s)
  5.         if s == t:
  6.                 return new_path
  7.         for next_node in graph[s].keys():
  8.                 if next_node not in new_path:
  9.                         return find_path(next_node, t, graph, new_path)
  10.         return []
  11.                
  12.  
  13. def find_flow(path, graph):
  14.        
  15.         flow = float('inf')
  16.         for i in range(1,len(path)):
  17.                 curr_node = path[i-1]
  18.                 next_node = path[i]
  19.                 capacity = graph[curr_node][next_node]
  20.                 flow = min(flow, capacity)
  21.         return flow
  22.        
  23. def update_graph(path, flow, graph):
  24.        
  25.         for i in range(1,len(path)):
  26.                 curr_node = path[i-1]
  27.                 next_node = path[i]
  28.                 graph[curr_node][next_node] -= flow
  29.                 if graph[curr_node][next_node] == 0:
  30.                         graph[curr_node].pop(next_node)
  31.                 graph[next_node][curr_node] = graph[next_node].get(curr_node,0) + flow
  32.  
  33. for _ in range(int(input())):
  34.        
  35.         inputs = input().split()
  36.         m, n, q = int(inputs[0]), int(inputs[1]), int(inputs[2])
  37.        
  38.         graph = {i:{} for i in range(0,m+n+2)}
  39.        
  40.         # node 1 to m is set A
  41.         # node m+1 to m+n is set B
  42.         for _ in range(q):
  43.                 inputs = input().split()
  44.                 A, B = int(inputs[0]), int(inputs[1])
  45.                 graph[A][B+m] = 1
  46.        
  47.         # node 0 is source
  48.         # node m+n+1 is sink
  49.         for i in range(1,m+1):
  50.                 graph[0][i] = 1
  51.         for i in range(1,n+1):
  52.                 graph[i+m][m+n+1] = 1
  53.        
  54.         max_flow = 0
  55.         path = find_path(0, m+n+1, graph)
  56.         while(len(path) > 0 and path[-1] == n):
  57.                 flow = find_flow(path, graph)
  58.                 max_flow += flow
  59.                 update_graph(path, flow, graph)
  60.                 path = find_path(0, m+n+1, graph)
  61.         output = str(max_flow) + " "
  62.         output += "Y" if max_flow == m else "N"
  63.         print(output)
Parsed in 0.022 seconds