Trimestre 2014 Primavera
Entrega: 23 de junio de 2014 a las 22:00.
El propósito de esta tarea es el de practicar algunos conceptos de
gráficas no dirigidas vistos en clase.
Imagine que se tiene un región G en la cual hay un conjunto V de
ciudades pequeñas unidas por un conjunto E de caminos, de los cuales
se conocen sus longitudes. Una compañía desea abrir una tienda en
alguna de estas ciudades y se enfrenta a la pregunta de en cuál de
ellas debe colocarla. Para ello se podrían tener varios criterios,
pero la compañía ha optado por el siguiente: abrirá la tienda en
aquella ciudad tal que la distancia promedio que se tenga que viajar
desde cualquier otra ciudad a esta sea la menor posible.
Por ejemplo, si V = {A, B, C, D} y los caminos tienen las longitudes
AB = 3, BC = 2, CD = 4 y DA = 2 entonces se tienen las siguientes
opciones:
colocar la tienda en A: la distancia de B a A es 3, de C a A
es 5 y de D a A es 2, el promedio es 10/3 = 3.33...
colocar la tienda en B: la distancia de A a B es 3, de C a B
es 2 y de D a B es 5, el promedio es 10/3 = 3.33...
colocar la tienda en C: la distancia de A a C es 5, de B a C
es 2 y de D a C es 4, el promedio es 11/3 = 3.66...
colocar la tienda en D: la distancia de A a D es 2, de B a D
es 5 y de C a D es 4, el promedio es 11/3 = 3.66...
de modo que lo mejor es poner la tienda en A o en B (que tienen el
mismo promedio).
Escribe un programa tiendaNN
que decida en qué ciudades se puede poner la tienda.
La entrada al programa consiste de un renglón con un entero N (la
cantidad de ciudades) seguido de N renglones con N enteros cada uno.
El entero A[i][j] en la columna i del renglón j es la longitud del
camino entre las ciudades i y j (excepto si el valor es 0 esto
significa que no hay camino). Puedes suponer que 2 <= N <= 100
y que 0 <= A[i][j] <= 100.
La salida del programa consiste de un renglón con un entero C, la
cantidad de ciudades distintas en las que se puede poner la tienda,
seguido de un renglón con C enteros ordenados ascendentemente, los
números de esas ciudades (considera que las ciudades están numeradas
de la 0 a la N-1).