Resolviendo el #TuentiContest: Problema 16 – The Bus Stations

Ya estoy en la recta final. Toca mi penúltimo problema, el problema 16. Debemos organizar el tráfico de autobuses de España. Nos piden enviar autobuses de una ciudad a otra, indicándonos cuántos pueden circular al mismo tiempo por las distintas calles. Otro problema de libro de grafos que en su versión teórica se llama Flujo Máximo. La solución está en Java. Recuerda que también puedes ver mis soluciones a los otros problemas de la competición. Este fue el último problema antes de la polémica recta final del concurso, en la que dejaban de explicar qué querían y pasaban a un formato más de adivinanza. Por ahora, centrémonos en el 16. Los problemas de grafos siempre me han gustado y a este en particular le tenía un respeto especial porque a pesar de que conocía el algoritmo y lo había implementado varias veces, nunca me había detenido a entender por qué funcionaba, hasta ahora. Aquí vuelve a ocurrir otro error de los organizadores. La explicación de los datos de entrada coincide con los casos de prueba pero no con el caso de ejemplo. Así que lo que me pasó fue que pensé que se habían equivocado en la explicación y lo implementé ajustándome al ejemplo, luego cuando probé el resto de casos me di cuenta que el error era el ejemplo, y tuve que cambiar la lectura de datos. Es increíble como algo tan delicado como las pruebas y los ejemplos haya tenido tantos fallos a lo largo de la competición. Supongo que será la novatada. Esperemos que no vuelva a ocurrir.

Análisis del problema De una forma similar al problema de BAZINGA, aquí nos dan la descripción entera de un grafo a través de su matriz de adyacencia, señalándonos la capacidad máxima de cada arista. En realidad el planteamiento del problema es bastante corto (un solo párrafo) y si no reconocías que se trataba de un problema de Flujo Máximo, probablemente tendrías muchos problemas para resolverlo. Es un problema difícil en sí mismo, solo que tiene una solución conocida. De nuevo, creo que lo pusieron para saber quiénes han estudiado informática y quiénes solo saben programar. El algoritmo que resuelve el problema se llama Ford-Fulkerson y está basado en dos ideas simples: la capacidad de un camino entre A y B viene determinada por la arista de menor capacidad (algo así como “la resistencia de una cadena viene dada por su eslabón más débil”) y mientras exista un camino entre A y B con capacidad mayor a cero, cubrimos ese camino con su capacidad máxima. Ya que estoy con ánimos de seguir dibujando, te muestro una imagen de las dos ideas.

Como ves, la capacidad máxima depende de la arista de capacidad mínima. En el caso de los caminos, los oscuros representan rutas que ya han cubierto su capacidad máxima y el claro es uno que aún admite más flujo, así que podríamos seguir enviando autobuses por allí hasta oscurecerlo. La página en inglés de Wikipedia describe con detalle el algoritmo y hasta tiene una implementación en Python a la que puedes echarle un vistazo. Aquí encontrarás la versión en Java.

Solución enviada

Mi solución implementa la clase Arco para representar las aristas del grafo. Cada arco contiene los indices de las ciudades involucradas (automáticamente asignados por mi), sus nombres, la capacidad máxima y el flujo, que inicialmente es cero. Adicionalmente, he implementado cinco funciones auxiliares: flujoMáximo, fordFulkerson, flujo, dfs y buildNet. La primera obtiene la respuesta final revisando el flujo de todas las aristas salientes de la ciudad de origen, una vez que ya se haya calculado la solución; la segunda función, como su nombre lo indica, es la implementación del algoritmo como tal, basado en las dos ideas que comenté anteriormente; flujo y dfs son las implementaciones de cada una de esas ideas respectivamente; finalmente, buildNet es la función que se encarga de la lectura de datos y de la creación del grafo con el que se quiere trabajar. El grafo lo represento como una lista de arcos mientras que la red de flujo sobre la que se calcula la solución la represento como una matriz de adyacencia. Las líneas resaltadas son las que obtienen la solución. También he resaltado el inicio de cada función auxiliar para que las encuentres rápidamente entre tanta línea.

import java.util.*;

class Arco {
  int capacidad;
  int flujo;
  int from;
  int to;
  String cityFrom;
  String cityTo;

  public Arco(){}

  public Arco(int i, int j){
    from = i;to = j;
  }

  public Arco(String data){
    String[] split = data.split(",");
    cityFrom = split[0];
    cityTo = split[1];
    capacidad = Integer.parseInt(split[2]);
  }
}

public class FlujoMaximo {
  static HashMap<String,Integer> nodos =
                      new HashMap<String, Integer>();
  static int lastNode=0;

  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    Scanner data;
    String query;
    while(scan.hasNextLine()){
      query = scan.nextLine().trim();
      data = new Scanner(query);
      data.nextInt();
      String source = data.next();
      String sink = data.next();
      if(!nodos.containsKey(source))
        nodos.put(source, lastNode++);
      if(!nodos.containsKey(sink))
        nodos.put(sink, lastNode++);

      ArrayList<Arco> arcos = buildNet(data);
      Arco[][] red = new Arco[lastNode][lastNode];

      for(Arco a : arcos) {
        red[a.from][a.to] = a;
        if(red[a.to][a.from]==null)
          red[a.to][a.from] = new Arco(a.to,a.from);
      }

      fordFerkulson(red,nodos.get(source),nodos.get(sink));
      int flujoMaximo = flujoMaximo(red,nodos.get(source));
      System.out.println(flujoMaximo);
    }
  }

  private static int flujoMaximo(Arco[][] red, int source){
    int maximo=0;
    for(int j=0;j<lastNode;j++){
      maximo += (red1[j]!=null)?red1[j].flujo:0;
    }
    return maximo;
  }

  private static void fordFerkulson(Arco[][] red,
                                    int source, int sink){
    LinkedList<Arco> path = new LinkedList<Arco>();
    dfs(red,source,sink,path,new boolean[lastNode]);
    while(path.size()>0){
      int flujo = flujo(path);
      for(Arco a:path){
        red[a.from][a.to].flujo += flujo;
        red[a.to][a.from].flujo -= flujo;
      }
      path = new LinkedList<Arco>();
      dfs(red,source,sink,path,new boolean[lastNode]);
    }
  }

  private static int flujo(LinkedList<Arco> path){
    int flujo = Integer.MAX_VALUE;
    for(Arco a: path){
      if(a.capacidad-a.flujo < flujo) {
        flujo = a.capacidad-a.flujo;
      }
    }
    return flujo;
  }

  private static void dfs(Arco[][] red, int source, int sink,
          LinkedList<Arco> path, boolean[] visitados){
    visitados1 = true;
    if(source == sink){
      return;
    }
    for(int j=0;j<lastNode;j++){
      Arco a = red1[j];
      if(a!=null){
        int residuo = a.capacidad-a.flujo;
        if(residuo > 0 && !visitados[a.to]){
          path.add(a);
          dfs(red,a.to,sink,path,visitados);
          if(!visitados[sink]){
            path.removeLast();
          }else{
            return;
          }
        }
      }
    }
    return;
  }

  private static ArrayList<Arco> buildNet(Scanner data) {
    ArrayList<Arco> red = new ArrayList<Arco>();
    while(data.hasNext()){
      Arco a = new Arco(data.next());

      if(!nodos.containsKey(a.cityFrom)){
        a.from = lastNode++;
        nodos.put(a.cityFrom, a.from);
      } else {
        a.from = nodos.get(a.cityFrom);
      }

      if(!nodos.containsKey(a.cityTo)) {
        a.to = lastNode++;
        nodos.put(a.cityTo, a.to);
      } else {
        a.to = nodos.get(a.cityTo);
      }

      red.add(a);
    }
    return red;
  }
}

Solución mejorada

En este caso, no se me ocurre algo concreto que mejorar. Es posible que una representación distinta del grafo pueda ayudar en la implementación. Sin embargo, creo que cada una de las funciones auxiliares es bastante legible. Se me acaba de ocurrir también que el DFS podría mezclarse con el cálculo de la capacidad máxima del camino (el método flujo) para dar ambas respuestas de una vez pero estaríamos sacrificando la modularidad, una mala práctica en nuestro mundo. Dada la falta de ideas, paso a darte el mando para que me comentes qué mejoras podemos agregar.

Y tú, ¿cómo lo resolviste?

One thought on “Resolviendo el #TuentiContest: Problema 16 – The Bus Stations

Deja un comentario