• API
• FAQ
• Tools
• Archive
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.
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
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.

Top