SHARE
TWEET

CH16 Bus

a guest Jun 20th, 2011 771 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.HashMap;
  4. import java.util.LinkedList;
  5. import java.util.Map;
  6. import java.util.Queue;
  7. import java.util.StringTokenizer;
  8.  
  9. /*
  10.  * Tuenti Contest
  11.  * Challenge 16 - Bus Stations
  12.  * Author: Pedro Antonio Pardal Jimena
  13.  * Email: pardal@alu.uma.es
  14.  */
  15.  
  16. public class BusStations
  17. {
  18.         private static int bfs( int[][] capacidades, int[] camino, int[] padres, int inicio, int fin )
  19.         {
  20.                 camino[inicio] = Integer.MAX_VALUE;
  21.                
  22.                 Queue<Integer> queue = new LinkedList<Integer>();
  23.                 queue.add( inicio );
  24.                
  25.                 while ( !queue.isEmpty() )
  26.                 {
  27.                         int u = queue.poll();
  28.                        
  29.                         for ( int v = 0; v < capacidades.length; v++ )
  30.                         {
  31.                                 if ( capacidades[u][v] != Integer.MAX_VALUE ) /* Hay arco */
  32.                                 {
  33.                                         /* Hay capacidad suficiente, y v no fue visitado antes */
  34.                                         if ( capacidades[u][v] > 0 && padres[v] == -1 )
  35.                                         {
  36.                                                 padres[v] = u;
  37.                                                 camino[v] = Math.min( camino[u], capacidades[u][v] );
  38.                                                
  39.                                                 if ( v != fin )
  40.                                                         queue.add( v );
  41.                                                 else
  42.                                                         return camino[fin];
  43.                                         }
  44.                                 }
  45.                         }                      
  46.                 }
  47.                
  48.                 return 0;
  49.         }
  50.        
  51.         private static int edmondsKarp( int[][] capacidades, int tam, int inicio, int fin )
  52.         {
  53.                 int maxFlujo = 0;
  54.                 int[][] flujos = new int[tam][tam];
  55.                 for ( int i = 0; i < tam; i++ )
  56.                         for ( int j = 0; j < tam; j++ )
  57.                                 flujos[i][j] = 0;              
  58.                
  59.                 while ( true )
  60.                 {
  61.                         int[] camino = new int[tam];
  62.                         int[] padres = new int[tam];
  63.                         /* Inicializar tabla de padres */
  64.                         for ( int i = 0; i < padres.length; i++ )
  65.                         {
  66.                                 padres[i] = -1;
  67.                         }
  68.                         padres[inicio] = -2; /* Para que el nodo inicial no sea redescubierto */
  69.                        
  70.                         /* Calcular un camino del nodo inicial al final en el grafo residual */
  71.                         int m = bfs( capacidades, camino, padres, inicio, fin );
  72.                        
  73.                         if ( m == 0 ) /* Si no hay camino, hemos terminado */
  74.                                 break;
  75.                        
  76.                         maxFlujo += m;
  77.                        
  78.                         /* Actualizar el grafo residual con el menor arco del camino */
  79.                         int v = fin;
  80.                        
  81.                         while ( v != inicio )
  82.                         {
  83.                                 int u = padres[v];
  84.                                 capacidades[u][v] -= m;
  85.                                 capacidades[v][u] += m;
  86.                                 v = u;
  87.                         }
  88.                 }
  89.                
  90.                 return maxFlujo;
  91.         }
  92.        
  93.         public static void main( String[] args )
  94.         {
  95.                 try
  96.                 {
  97.                         BufferedReader reader = new BufferedReader( new InputStreamReader( System.in ) );
  98.                        
  99.                         while ( reader.ready() )
  100.                         {
  101.                                 String linea = reader.readLine();
  102.                                
  103.                                 StringTokenizer st = new StringTokenizer( linea, " " );
  104.                                
  105.                                 int tam = Integer.parseInt( st.nextToken() );
  106.                                 String inicio = st.nextToken();
  107.                                 String fin = st.nextToken();
  108.                                
  109.                                 int[][] capacidades = new int[tam][tam];
  110.                                 for ( int i = 0; i < tam; i++ )
  111.                                         for ( int j = 0; j < tam; j++ )
  112.                                                 capacidades[i][j] = Integer.MAX_VALUE;                         
  113.                                
  114.                                 Map<String, Integer> nodos = new HashMap<String, Integer>();
  115.                                 nodos.put( inicio, 0 );
  116.                                 nodos.put( fin, 1 );                           
  117.                                
  118.                                 while ( st.hasMoreTokens() )
  119.                                 {
  120.                                         String arco = st.nextToken();
  121.                                        
  122.                                         StringTokenizer st2 = new StringTokenizer( arco, "," );
  123.                                        
  124.                                         String desde = st2.nextToken();
  125.                                         String hasta = st2.nextToken();
  126.                                         int capacidad = Integer.parseInt( st2.nextToken() );
  127.                                        
  128.                                         if ( !nodos.containsKey( desde ) )
  129.                                                 nodos.put( desde, nodos.size() );
  130.                                        
  131.                                         if ( !nodos.containsKey( hasta ) )
  132.                                                 nodos.put( hasta, nodos.size() );
  133.                                        
  134.                                         int desdeIdx = nodos.get( desde );
  135.                                         int hastaIdx = nodos.get( hasta );
  136.                                        
  137.                                         capacidades[desdeIdx][hastaIdx] = capacidad;
  138.                                 }
  139.                                
  140.                                 int result = edmondsKarp( capacidades, tam, 0, 1 );
  141.                                
  142.                                 System.out.println( result );
  143.                         }
  144.                 }
  145.                 catch ( Exception e )
  146.                 {
  147.                         System.err.println( "Error en el formato de entrada." );
  148.                         e.printStackTrace( System.err );
  149.                 }
  150.         }
  151. }
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