Tarea 2 de Almacenamiento y Recuperación de la
Información
Trimestre 2009 Primavera
Entrega: 7 de julio de 2009 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 estará en el archivo tienda.ent y 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 deberá estar en el archivo tienda.sal y 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).