• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# BusStations

alefhidalgo Jun 20th, 2011 755 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import java.util.HashMap;
2. import java.util.Map;
3. import java.util.Scanner;
4.
5. /**
6.  * Tuenti Programming Contest
7.  * Challenge 16: The Bus Stations
8.  *
9.  * @author alefhidalgo [at] gmail [dot] com
10.  */
11. public class BusStations {
12.         /* Required variables for Edmonds-Karp algorithm */
13.         public static final int WHITE = 0, GRAY = 1, BLACK = 2;
14.         private int[][] flow, capacity, residualCapacity;
15.         private int[] parent, color, queue;
16.         private int[] minCapacity;
17.         private int size, sourceStation, sinkStation;
18.
19.         private Map<String, Integer> stationsMap; /* Map Station->Index */
20.         private int stationsIndexCounter = 0;
21.
22.         /**
23.          * Constructor
24.          * @param n Number of stations
25.          * @param stationFrom
26.          * @param stationTo
27.          */
28.         public BusStations(int n, String stationFrom, String stationTo) {
29.                 this.size = n;
30.                 capacity = new int[n][n];
31.                 stationsMap = new HashMap<String, Integer>(n);
32.                 sourceStation = getNodeIndex(stationFrom);
33.                 sinkStation = getNodeIndex(stationTo);
34.         }
35.
36.         /**
37.          * Edmonds-Karp algorithm with O(V³E) complexity
38.          *
39.          * @return maxFlow between stationFrom to stationTo
40.          */
41.         public int maxFlow() {
42.                 int maxFlow = 0;
43.                 flow = new int[size][size];
44.                 residualCapacity = new int[size][size];
45.                 parent = new int[size];
46.                 minCapacity = new int[size];
47.                 color = new int[size];
48.                 queue = new int[size];
49.
50.                 for (int i = 0; i < size; i++)
51.                         for (int j = 0; j < size; j++)
52.                                 residualCapacity[i][j] = capacity[i][j];
53.
54.                 while (BFS(sourceStation)) {
55.                         maxFlow += minCapacity[sinkStation];
56.                         int v = sinkStation, u;
57.                         while (v != sourceStation) {
58.                                 u = parent[v];
59.                                 flow[u][v] += minCapacity[sinkStation];
60.                                 flow[v][u] -= minCapacity[sinkStation];
61.                                 residualCapacity[u][v] -= minCapacity[sinkStation];
62.                                 residualCapacity[v][u] += minCapacity[sinkStation];
63.                                 v = u;
64.                         }
65.                 }
66.
67.                 return maxFlow;
68.         }
69.         /**
71.          *
72.          * @param stationA
73.          * @param stationB
74.          * @param maxFlow
75.          */
77.                 int indexA = getNodeIndex(stationA);
78.                 int indexB = getNodeIndex(stationB);
79.                 capacity[indexA][indexB] = maxFlow;
80.         }
81.
82.
83.
84.         /**
85.          * Get node index from stationName
86.          *      stationName is mapped if station does not exists in stationsMap
87.          * @param stationName
88.          * @return
89.          */
90.         private int getNodeIndex(String stationName) {
91.                 int pos = -1;
92.                 if (stationsMap.containsKey(stationName)) {
93.                         pos = stationsMap.get(stationName);
94.                 } else {
95.                         pos = stationsIndexCounter++;
96.                         stationsMap.put(stationName, pos);
97.                 }
98.                 return pos;
99.         }
100.
101.
102.         /**
103.          * BFS Breadth First Search in O(V<sup>2</sup>)
104.          * @param source
105.          * @return
106.          */
107.         private boolean BFS(int source) {
108.                 int first, last;
109.                 for (int i = 0; i < size; i++) {
110.                         color[i] = WHITE;
111.                         minCapacity[i] = Integer.MAX_VALUE;
112.                 }
113.                 first = last = 0;
114.                 queue[last++] = source;
115.                 color[source] = GRAY;
116.
117.                 // While "queue" not empty..
118.                 while (first != last) {
119.                         int v = queue[first++];
120.                         for (int u = 0; u < size; u++)
121.                                 if (color[u] == WHITE && residualCapacity[v][u] > 0) {
122.                                         minCapacity[u] = Math.min(minCapacity[v],       residualCapacity[v][u]);
123.                                         parent[u] = v;
124.                                         color[u] = GRAY;
125.                                         if (u == sinkStation)
126.                                                 return true;
127.                                         queue[last++] = u;
128.                                 }
129.                 }
130.                 return false;
131.         }
132.
133.         public static void main(String args[]) {
134.                 BusStations busStations = null;
135.                 Scanner scanner = new Scanner(System.in);
136.                 Scanner lineScanner = null;
137.                 Scanner stationsScanner = null;
138.                 while (scanner.hasNextLine()) {
139.                         lineScanner = new Scanner(scanner.nextLine());
140.                         int nStations = Integer.parseInt(lineScanner.next());
141.                         String stationFrom = lineScanner.next();
142.                         String stationTo = lineScanner.next();
143.                         /* new BusStations */
144.                         busStations = new BusStations(nStations, stationFrom, stationTo);
145.                         while (lineScanner.hasNext()) {
146.                                 stationsScanner = new Scanner(lineScanner.next());
147.                                 stationsScanner.useDelimiter(",");
148.                                 String stationA = stationsScanner.next();
149.                                 String stationB = stationsScanner.next();
150.                                 int maxFlow = Integer.parseInt(stationsScanner.next());