Olá meus amigos nerds. Como a zueira não tem limites, eu não poderia deixar a data de ontem passar em branco. E para isso, nada melhor do que resolver um problema que tem 'de volta para o futuro' no nome e trata de viagens e fluxos. Hoje vamos ajudar nossos amigos a voltar da Alemanha gastando o mínimo possível em passagens aéreas. Já que é isso que o problema 1761. Back to the future nos pede para fazer. (Puts, tinha que ter postado esse problema ontem kkk). Mais especificamente, dadas as rotas aéreas e o número de lugares livres por avião, determinar qual é o mínimo possível que um grupo de d amigos precisa gastar para conseguir viajar entre duas cidades a e b dadas.
Solução
Com um nome desses, esse problema não poderia ser fácil. Como em muitos problemas que envolvem rotas, uma abordagem usando grafos é uma boa ideia. As cidades seriam os vértices de forma que cada vôo seria uma aresta. Cada aresta teria um custo (valor da passagem) e uma capacidade (número de acentos livres). Se você conhece um pouco sobre fluxo máximo em grafos, você deve estar vendo onde quero chegar com essa modelagem.
O problema do fluxo máximo consiste em, encontrar qual seria o maior fluxo, que se poderia transferir de um nó de origem para um nó de destino, respeitando a capacidade de transferir fluxo de cada aresta. Uma analogia seria um sistema hidráulico com canos interligando vários pontos...
Uma variação desse problema é o fluxo máximo a custo mínimo, ou seja, onde cada aresta possui um custo associado, para transportar o fluxo. Como vocês podem observar, nosso problema é praticamente esse.
Fluxo máximo a custo mínimo pode ser resolvido usando-se o algoritmo de Edmonds-Karp. Note que, no problema de fluxo, cada aresta tem duas grandezas associadas a ela, um custo e uma capacidade. A ideia desse algoritmo é ir encontrando caminhos da origem para o destino e transferindo o máximo de fluxo que esse caminho suporta. Mais algoritmicamente: (1) encontre um caminho mínimo (em relação ao custo) da origem ao destino. (2) Verifique qual é a aresta desse caminho que admite a menor capacidade. (3) Transfira, por esse caminho, um fluxo igual a essa capacidade. (4) De cada aresta do caminho subtraia a capacidade transportada. (5) Continue com esse procedimento até que não haja mais caminhos da origem para o destino com todas as arestas com capacidades maiores que 0. Observe que o caminho mínimo muda a cada iteração, pois reduzir a capacidade de uma aresta a 0, corresponde a 'tirar' essa aresta do grafo.
Oras, mas esse problema do fluxo máximo é o mesmo do problema que queríamos resolver, de modo que, o custo do fluxo máximo no grafo dos vôos é a resposta! Errado! Observe que no problema do fluxo máximo assume-se que a origem tem capacidade de produzir um fluxo tão grande quanto o grafo possa aguentar. No nosso caso, o número de passageiros é limitado. Mas se você pensar um pouquinho vai ver que é só parar o algoritmo quando tivermos transportado todos nossos amigos de volta para o Brasil.
O problema do fluxo máximo consiste em, encontrar qual seria o maior fluxo, que se poderia transferir de um nó de origem para um nó de destino, respeitando a capacidade de transferir fluxo de cada aresta. Uma analogia seria um sistema hidráulico com canos interligando vários pontos...
Uma variação desse problema é o fluxo máximo a custo mínimo, ou seja, onde cada aresta possui um custo associado, para transportar o fluxo. Como vocês podem observar, nosso problema é praticamente esse.
Fluxo máximo a custo mínimo pode ser resolvido usando-se o algoritmo de Edmonds-Karp. Note que, no problema de fluxo, cada aresta tem duas grandezas associadas a ela, um custo e uma capacidade. A ideia desse algoritmo é ir encontrando caminhos da origem para o destino e transferindo o máximo de fluxo que esse caminho suporta. Mais algoritmicamente: (1) encontre um caminho mínimo (em relação ao custo) da origem ao destino. (2) Verifique qual é a aresta desse caminho que admite a menor capacidade. (3) Transfira, por esse caminho, um fluxo igual a essa capacidade. (4) De cada aresta do caminho subtraia a capacidade transportada. (5) Continue com esse procedimento até que não haja mais caminhos da origem para o destino com todas as arestas com capacidades maiores que 0. Observe que o caminho mínimo muda a cada iteração, pois reduzir a capacidade de uma aresta a 0, corresponde a 'tirar' essa aresta do grafo.
Oras, mas esse problema do fluxo máximo é o mesmo do problema que queríamos resolver, de modo que, o custo do fluxo máximo no grafo dos vôos é a resposta! Errado! Observe que no problema do fluxo máximo assume-se que a origem tem capacidade de produzir um fluxo tão grande quanto o grafo possa aguentar. No nosso caso, o número de passageiros é limitado. Mas se você pensar um pouquinho vai ver que é só parar o algoritmo quando tivermos transportado todos nossos amigos de volta para o Brasil.
Implementação
O problema afirma que nossos amigos tem pouco dinheiro. Mas não deixe se enganar, o custo máximo da viajem de todos pode chegar a 10^15 reais (Imagina eu com esse dinheiro todo, dava até para começar a construir minha própria máquina do tempo :D). Felismente 10^15 cabe em um long long.
O código não está la muito bonito (tempos de maratona, lembra?), me desculpem pelas macros não muito elegantes. Mas também, vocês tem que me dar um desconto, fluxo máximo usa até um dijkstra como uma pequena parte dele.
O código não está la muito bonito (tempos de maratona, lembra?), me desculpem pelas macros não muito elegantes. Mas também, vocês tem que me dar um desconto, fluxo máximo usa até um dijkstra como uma pequena parte dele.
Nenhum comentário:
Postar um comentário