← Volver a los ejercicios

Cambiar un vuelo para acortar el peor trayecto

El problema de cierre de la sesión, UVa 11695. Hay n ciudades y n−1 vuelos, de modo que entre dos cualesquiera hay una sola ruta. Se quita un vuelo y se pone otro, buscando que el mayor número de trasbordos quede lo más pequeño posible. Aquí se prueba cada corte y se ve por qué conviene volver a unir por los centros.

El problema: vjudge.net/problem/UVA-11695. Ahí están el enunciado completo y el envío.

1. La red de vuelos

Diámetro actual: trasbordos.

2. Quite un vuelo

Al quitarlo quedan dos pedazos. Cada uno tiene su diámetro y su centro, y la mejor forma de volver a unirlos es con un vuelo entre los dos centros.

3. El mejor cambio posible

Menor diámetro que se puede dejar

4. Cómo leer la entrada

La primera línea trae el número de casos. Cada caso trae n y después n−1 líneas con un par de ciudades. Con scanf alcanzan dos ciclos:

int casos;
scanf("%d", &casos);
for (int caso = 0; caso < casos; caso++) {
  int n;
  scanf("%d", &n);
  vector<int> a(n - 1), b(n - 1);
  for (int i = 0; i < n - 1; i++) {
    scanf("%d %d", &a[i], &b[i]);
  }
  /* aquí se prueban las n-1 aristas */
}

Las ciudades vienen numeradas desde 1, así que o se les resta uno al leerlas o se reservan n+1 casillas. La salida son tres líneas por caso: el diámetro nuevo, el vuelo que se quita y el que se pone.

5. Para llevarse

Sin solución aquí. Pruebe las tres redes y mire dónde caen las aristas que dan el mejor resultado: siempre están cerca de la mitad del camino más largo. Explique por qué unir dos pedazos por sus centros no se puede mejorar, y después calcule cuánto cuesta el algoritmo completo si por cada una de las n−1 aristas se resuelven las dos mitades en tiempo lineal.

Enunciado y envío: vjudge.net/problem/UVA-11695