|
|
Problema E - To win, or not to win: that is the question |
Autor: Margarida Mamede (Universidade Nova de Lisboa)
Tipo de problema: Grafos (ordenação topológica)
Um grafo direccionado é a estrutura de dados que intuitivamente armazena os dados fornecidos pelas regras. Os nós são os concorrentes, e existe uma ligação entre dois nós se um dado concorrente só pode ganhar prémio se um outro também ganhar.
Seja suc(i) o número de "sucessores" do nó i, ou seja, o número de nós "alcançáveis" a partir do nó i (aqueles para os quais existe um caminho que começa em i e termina neles). Estes são os nós que correspondem a pessoas que têm de ganhar um prémio antes de i ganhar. Para os calcular, basta fazer, por exemplo, uma simples pesquisa em profundidade no grafo, começando em i.
Seja ant(i) o número de "antecessores" do nó i, ou seja, o número de nós a partir dos quais i é "alcançável" (aqueles para os quais existe um caminho que começa neles e termina em i. Estes são os nós que correspondem a pessoas que só podem ganhar prémio se t também ganhar. Para os calcular, se considerarmos o grafo inverso (ou seja, os mesmos nós e as mesmas ligações, mas com direcção invertida), basta também uma simples pesquisa em profundidade no grafo. Dito de outro, os antecessores de um nós, são os seus sucessores no grafo invertido.
Com estas definições, o problema fica agora fácil de resolver. Seja P o número de prémios e A o número de aces, as pessoas, ou seja, os nós do grafo. Se nos for perguntado o resultado para a pessoa i:
Ligações interessantes: