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.
Diámetro actual: trasbordos.
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.
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.
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