SHARE
TWEET

Tuenti Contest - Solution challenge 16

Yukino Jun 28th, 2011 995 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/python
  2. import sys
  3.  
  4. # Challenge 16 is the Maximum Flow Problem: find a feasible flow
  5. # (that is, without exceeding the capacity of the network, in
  6. # this case the number of buses that can travel from one station to another)
  7. # through a network with a single source (origin station)
  8. # and single sink (destination city), that is maximum
  9. # http://en.wikipedia.org/wiki/Maximum_flow_problem
  10.  
  11. def edmondsKarp(C, source, sink):
  12.         """
  13.         Implementation of Edmonds-Karp algorithm for computing max-flow in a network
  14.         It is a variation of the Ford-Fulkerson method. I tried that before and it was
  15.         too slow for the test case, so I gave this one a go.
  16.  
  17.         The code is almost a translation from the pseudocode in Wikipedia:
  18.         http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm#Pseudocode
  19.        
  20.         C is the capacity matrix and the function returns the maximum flow from source
  21.         to sink
  22.         """
  23.         n = len(C) # number of nodes/stations
  24.        
  25.         # residual capacity from u to v is C[u][v] - F[u][v]
  26.         F = [[0]*n for i in xrange(n)]
  27.        
  28.         while True:
  29.                 # find by BFS shortest path which has available capacity
  30.                 # this will be the augmenting path (backwards, with parents)
  31.                 path = bfs(C, F, source, sink)
  32.                 if not path:
  33.                         break
  34.                        
  35.                 # backtrack search from destination
  36.                 flow = min(C[u][v] - F[u][v] for u,v in path)
  37.                
  38.                 # traverse found path to update flow
  39.                 for u,v in path:
  40.                         F[u][v] += flow
  41.                         F[v][u] -= flow
  42.  
  43.         return sum(F[source][i] for i in xrange(n))
  44.  
  45. def bfs(C, F, source, sink):
  46.         """
  47.         In the Edmonds-Karp algorithm, the new augmenting path must be the shortest path with
  48.         available capacity, and it is found by breadth-first search
  49.         This is basically the only difference with the Ford-Fulkerson algorithm
  50.         """
  51.         queue = [source]                
  52.         paths = {source: []}
  53.         while len(queue) > 0:
  54.                 u = queue.pop(0)
  55.                 # for each station/node
  56.                 # (Note: in Wikiepdia's pseudocode they only consider neighbours of u here. I
  57.                 # consider all nodes, and for those that aren't connected to u, C[u,v]=0)
  58.                 for v in xrange(len(C)):
  59.                         # if there is available capacity, and v is not seen before in search:  
  60.                         if C[u][v] - F[u][v] > 0 and v not in paths:
  61.                                 paths[v] = paths[u] + [(u,v)]
  62.                                 if v == sink:
  63.                                         return paths[v]
  64.                                 queue.append(v)
  65.         # there is no path
  66.         return False
  67.  
  68. # read cases
  69. for line in sys.stdin:
  70.         case = line.split()
  71.         n, orig, dest = case[0:3]
  72.         n = int(n)
  73.        
  74.         # capacity matrix
  75.         C = [[0]*n for i in xrange(n)]
  76.    
  77.         cities = {orig:0, dest:1}
  78.         ic = 2
  79.         roads = {}
  80.        
  81.         # build capacity matrix
  82.         for r in case[3:]:
  83.                 source, destination, cap = r.split(',')        
  84.                 isource, idestination = 0, 0
  85.                
  86.                 if not source in cities:
  87.                         cities[source] = ic
  88.                         isource = ic
  89.                         ic += 1
  90.                 else:
  91.                         isource = cities[source]
  92.                        
  93.                 if not destination in cities:
  94.                         cities[destination] = ic
  95.                         idestination = ic
  96.                         ic += 1
  97.                 else:
  98.                         idestination = cities[destination]     
  99.  
  100.                 C[isource][idestination] = int(cap)    
  101.                        
  102.         print edmondsKarp(C, 0, 1)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top