PKU 2060 - Taxi Cab Scheme

Autor da análise: raphael_ribasraphael_ribas

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2060

Resumo

É dado uma lista de corridas de taxi e pede-se o menor número de taxistas necessários para atender todas as corridas. Para cada corrida é dada a hora de início, o local de início e o destino. Um taxista só pode atender uma corrida se ele chegar antes da hora de início. A cidade é representada por um grid. Um taxista leva um minuto para percorrer uma quadra.

Solução

Seja G um grafo dirigido. O grafo G possui um vértice para cada corrida, e uma aresta uv pertence à G se é possível um taxista atender a corrida v logo após ter atendido a corrida u. O conjuno de corridas que um taxista pode atender corresponde a um caminho no grafo G. Como queremos o menor número de taxistas, então queremos o menor número de caminhos que cobrem o grafo G. Agora o problema se resume a encontrar a menor cobertura por caminhos de G. Esse problema é NP-difícil no caso geral, é fácil provar isso fazendo redução do problema de caminho hamiltoniano para este problema. Mas nesse caso, como o taxista não pode voltar no tempo, o grafo não possui circuitos e o problema é polinomial.

Note que o número de caminhos depende do número total de arestas em todos os caminhos, para ser mais preciso, o número de caminhos é igual ao número de vértices menos o número de arestas de todos os caminhos. Essa informação é útil, nos permite ver o problema de outra fora. Agora queremos escolher o maior número de arestas que cobre o grafo de uma certa forma. Essa forma é tal que só podemos tomar uma aresta de saída e uma de entrada para cada vértice. Isso já está parecendo com emparelhamento, só que ainda podemos tomar duas arestas incidentes no mesmo vértice. Mas se construirmos outro grafo H, que para cada vértice de G possui um vértice para as arestas que chegam e outro vértice para as aresta que saem e as mesmas arestas de G redistribuídas conforme a definição dos vértices, temos exatamento o problema do emparelhamento máximo. Cada vértice de H só possui ou arestas de saída ou arestas de entrada então só precisamos de uma aresta cobrindo para cada vértice. Então pelo que foi dito anteriormento o menor número de caminhos que cobre o grafo G é igual ao número de vértices de G menos o número de arestas do emparelhamento máximo de H. Observe também que H é um grafo bipartido, isso ajuda na escolha do algoritmo de emparelhamento. Nesse caso o algoritmo húngaro é suficiente e possui complexidade $O(VE)$.

O problema pode ser resolvido de outras formas, uma delas é com fluxo máximo de custo mínimo. Cada corrida recebe um custo -1 no grafo e fluxo 1, então inserimos uma aresta de cada vez com fluxo 1 que corresponde a um taxista extra e rodamos uma iteração do algoritmo de fluxo máximo de custo mínimo, repetimos isso até o custo do fluxo chegar a -M. Parece uma solução válida, mas deve ser difícil passar no tempo limite ou impossível. O algoritmo de emparelhamento máximo é bem mais rápido na prática.

Sobre o algoritmo húngaro veja http://en.wikipedia.org/wiki/Hungarian_algorithm .

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License