Problema F - Book Hand Delivery

Autor: André Restivo (Faculdade de Engenharia da Universidade do Porto)
Tipo de problema: Grafos (caminho mínimo/Dijkstra)

A principal dificuldade do problema é perceber qual a melhor maneira de representar os dados de entrada. Intuitivamente, um grafo aparece como uma estrutura de dados adequada. Mas o que colocar como nós e ligações? A escolha vai influenciar a dificuldade da implementação e a eficiência da solução, que passa por encontrar um caminho mínimo entre duas pessoas.

Vejamos três hipóteses diferentes de representação para os nós (Seja P o número de pessoas):

Nós "pessoa/dia": neste caso um nó é um par (pessoa,dia). Uma ligação entre dois nós existe se ambas as pessoas estão na mesma actividade no mesmo dia (é directamente calculável a partir da matriz dada no input e as ligações têm todas o mesmo peso de zero dias). Existem também sempre ligações entre a mesma pessoa em dias diferentes, com os pesos correspondentes. Neste caso teremos um grafo com 7*P nós.
Nós "pessoa": neste caso um nó é uma pessoa. A criação das ligações e a sua "navegação" para caminhos mínimos é muito "tricky", pois é preciso ter em conta os diferentes sítios onde cada pessoa está, e em que dia estamos. É uma aproximação onde é fácil cometer pequenos erros de implementação.
Nós "actividade/dia": neste caso um nó é um par (actividade,dia). Uma ligação existe se a mesma pessoa está numa dada actividade num dia, e depois vai para outra actividade noutro dia (com o peso da ligação a ser a diferença de número de dias). Estas ligações são obtidas directamente a partir da matriz dada e o grafo fica apenas com 26*7 nós, porque no máximo existem 26 actividades.

A segunda hipótese dada é propícia a pequenos erros, e era de evitar. Dado que o número de pessoas máximo é de 1000, a primeira hipótese cria um grafo relativamente grande (7000 nós), pelo que a solução recomendada passa por usar a última hipótese de grafo dada, com apenas 182 nós.

Para descobrir o caminho mínimo podemos usar o clássico (e frequente em concursos) algoritmo de Dijkstra. Tendo em conta que o número de nós é pequeno, bastaria uma implementação quadrática - O(N^2) do algoritmo. Uma vez que se queria o caminho mínimo entre duas pessoas, que não correspondem a nós do 3º grafo, poderíamos por exemplo criar dois nós virtuais, um para a pessoa inicial, outro para a final, com ligações de custo zero para as respectivas actividades/dia.

O autor do problema, o André Restivo, criou um documento com as imagens das três alternativas de representação de grafos:

3 possíveis representações do grafo (PDF produzido por André Restivo, FEUP, o autor do problema)

Ligações interessantes: