Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
10044 – Erdos Numbers

El problema es de Grafos y se puede solucionar con un BFS.
El problema habla acerca de Paul Erdos (Que fue un gran matemático).
En la descripción de la entrada nos dan una lista de publicaciones en las que en algunas participo Erdos y otros colaboradores y en otras no.
Una vez leída la entrada, viene una lista de nombres, y a cada uno de ellos hay que calcularle a lo que el problema denomina “Numero de Erdos”.

Para calcular el numero pedido, el problema lo define como el numero de relaciones que hay para que alguien llegara a publicar algo con Erdos.
Las personas que publicaron directamente con el, tienen un Numero de Erdos igual a 1.
Las personas que publicaron con alguien que publico con Erdos, tienen un Numero de Erdos igual a 2.
Una persona relacionada con la persona del punto anterior, tiene un Numero de Erdos igual a 3.
Y así sucesivamente.

Si la persona no esta relacionada de ninguna manera con Erdos, se imprime la palabra “infinity”.
La solución consiste en generar un grafo a partir de las relaciones de los artículos y utilizar un BFS desde el nodo que corresponde a Erdos e ir guardando la distancia con la cual llegamos a cada nodo.
Al momento de la salida, si el nombre no fue visitado por el BFS o el nombre no existe en la base de datos de nombres que estan en las publicaciones, se imprime “infinity”, de lo contrario, la distancia que corresponda.
El BFS solo se ejecuta 1 vez y se accede a las consultas en tiempo constante.
El procesamiento de la entrada es algo complicado, pero es posible utilizando istringstream en C++ o StringTokenizer en Java, combinándolo con Mapas en C++ o HashMap en Java.

Para la separacion de los nombres en la linea de cada articulo, un nombre viene delimitado del lado derecho cuando encontramos una coma(,) o dos puntos(:) y antes de el hay un punto(.).
Ejemplo:

Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrices

El primer nombre es
Smith, M.N.
Se puede observar que, antes de la coma(,), hay un punto, así que la cadena empieza desde el principio de la cadena hasta el punto antes de la coma.
El segundo y el tercero se obtienen de manera similar, solo que el tercero se obtiene con los dos puntos(:)
El resto de la cadena es irrelevante.


Código en C++

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: