Tarea 4 de Almacenamiento y Recuperación de la Información

Trimestre 2013 Primavera
Entrega: 10 de junio de 2013 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:
  1. 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...
  2. 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...
  3. 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...
  4. 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).

Ejemplo

Entrada 1
Salida 1
Entrada 2
Salida 2
4
0 3 0 2
3 0 2 0
0 2 0 4
2 0 4 0
2
0 1
4
0 0 0 1
0 0 0 2
0 0 0 3
1 2 3 0
1
3