2533 - Connecting Cities (COJ)

por
Edit
Link al problema2533 - Connecting Cities

Dificultad: Medio

Problema:
Dado un conjunto de $N$ ($1 ≤ N ≤ 2000$) ciudades y $M$ ($0 ≤ M ≤ 50000$) carreteras cada una con un costo $P_i$ ($0 ≤ P_i ≤10^7$) de construcción distinto y un costo $C$ ($0 ≤ C ≤10^7$) por construir un aeropuerto, determinar el menor costo para conectar las $N$ ciudades. En este problema el aeropuerto cumple una función peculiar, ya que una carretera que va de una ciudad A a una ciudad B funciona como una arista bidireccional en un grafo; mientras que colocar un aeropuerto en una ciudad A forma una arista bidireccional con cualquiera otra ciudad que tenga un aeropuerto.

Solución:
Del problema mismo sabemos que para que dos ciudades se consideren conectadas debe existir una o varias aristas entre ellas. También sabemos que para obtener el costo mínimo la forma final de las conexiones debe ser un árbol (para evitar ciclos y por tanto aristas innecesarias), ya que en un árbol solo ocuparíamos $N - 1$ aristas. De inmediato el problema nos suena como a un simple árbol de mínima expansión... pero, ¿qué sucede con los aeropuertos?

El problema nos indica que pueden existir desde $0$ hasta $50000$ carreteras, por lo cual nosotros podemos esperar que existan ciudades a las cuales no es posible llegar por ninguna carretera y por lo tanto tratar de considerarlos en un árbol de mínima expansión es imposible (llamaremos componente conexa a un conjunto de $n$ ciudades unidas con $n - 1$ carreteras), es ahí donde los aeropuertos tienen una de sus funciones principales. Otra función de los aeropuertos se da cuando construir una carretera entre A y B es más costoso que construir un áeropuerto en A y B.

Recapitulando: sabemos que pueden existir varias componentes conexas, sabemos que construyendo un aeropuerto en cada una de ellas garantizaría que estén conectadas, sabemos que a veces el costo de construir una carretera entre dos ciudades es mayor al de poner aeropuertos en ellas y por último sabemos que queremos obtener el menor costo para conectarlas todas.

Para resolverlo, partiremos de que cada una de las $N$ ciudades tiene un áeropuerto y por tanto están todas conectadas lo cual tendrá un costo $C_0$, posteriormente iremos uniendo (como si estuvieramos formando un árbol de mínima expansión) a cada unión quitaremos un aeropuerto, ya que no es necesario una vez que exista una carretera entre dos ciudades, porque estas estarían conectadas de todos modos, al hacer esto obtendremos un costo $C_i$ ($1 ≤ i ≤ Z$, $Z$ es el número de uniones que es posible realizar), lo que nos queda por hacer extraer el valor mínimo de todos los $C_i$ para obtener la respuesta.

Lo único que resta por considerar es que de este modo de resolver el problema puede suceder que al final nos quede una sola componente conexa y por tanto un solo aeropuerto, lo cual representa un gasto innecesario y por tanto no debe ser parte de nuestra solución.

Complejidad: $O(M)$ donde $M$ es el número de carreteras

Código (C++):
Definiremos una función join(a, b) que intenta unir a con b y devuelve true si la unión fue posible. En un vector denominado roads tendremos las carreteras (con su origen 'o' y destino 'd') ordenadas de menor a mayor costo 'c'.

long long int ans = N * C;
long long int roadCost = 0;
int airports = N;
for(int i = 0; i < roads.size(); i++){
 if(join(roads[i].o, roads[i].d)){
  roadCost += roads[i].c;
  airports--;
  ans = min(ans, roadCost + airports * C);
 }
}
if(airports == 1)
 ans = min(ans, roadCost);
pritnf("%lld\n", ans);

4 comentarios on "2533 - Connecting Cities (COJ)"

  1. Como hago el join(); xD ? y oiga señor que no es if(!join) ???

    ResponderEliminar
    Respuestas
    1. join es una operación aplicable a la estructura union-find, en este caso la función devuélve verdadero si no es que los dos nodos ya estaban dentro de una misma componente conexa.

      De lo segundo: Cada vez que se realiza una unión 'join' nos devolverá 'true', y cada vez que se realice una unión debemos restar un aeropuerto, por eso es if(join... y no if(!join...

      Eliminar
  2. bool mismo(int a, int b){
    if(raiz(a)==raiz(b))
    return true;
    return false;
    }
    En este caso las unes si no estaban unidas porque si las unes y ya estaban unidas hará conexiones de más y dejará de ser un árbol, a lo mejor depende de la implementación de cada quien

    ResponderEliminar
    Respuestas
    1. Ahhm, por eso especifiqué qué es lo que hace join. Yep, es cuestión de implementación.

      Eliminar