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.         /**
  70.          * addStationLink Add road between two stations with a maxFlow
  71.          *
  72.          * @param stationA
  73.          * @param stationB
  74.          * @param maxFlow
  75.          */
  76.         public void addStationLink(String stationA, String stationB, int maxFlow) {
  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());
  151.                                 /* Add link between stations */
  152.                                 busStations.addStationLink(stationA, stationB, maxFlow);
  153.                         }
  154.                         //Print maxFlow
  155.                         System.out.println(busStations.maxFlow());
  156.                 }
  157.  
  158.         }
  159. }
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