Olá meus amigos nerds. Hoje vamos ajudar a polícia canadense a decidir o número máximo de policiais que podem ter um cavalo para montar. Já que é isso que o problema 1751. A lei vai a Cavalo! nos pede para fazer. Mais especificamente, dadas as afinidades entre cavalos e cavaleiros; e o número de cavaleiros que podem montar cada cavalo, determinar o número máximo de policiais que podem ter um cavalo para montar em uma atribuição entre cavalos e cavaleiro.
Solução
Esse problema envolve uma atribuição (match) entre cavalos e cavaleiros, uma boa forma de modelar a solução de problemas assim é usando grafos. Considere o grafo bipartido onde os vértices representam os cavalos e cavaleiros. Sendo que existe uma aresta entre dois vértices se o cavalo é compatível com o cavaleiro. Além disso, a cada vértice que representa um cavalo vou atribuir uma capacidade c igual ao número de cavaleiros que podem montar esse cavalo. Do mesmo modo, para cada vértice que representa um cavaleiro vou atribuir uma capacidade (igual a 1, já que cada cavaleiro pode montar apenas 1 cavalo).
O número máximo de cavaleiros que poderiam ter um cavalo para montar pode ser calculado como o fluxo máximo que pode passar por esse grafo, considerando-se os cavaleiros como sources e os cavalos como sinks. A ideia por traz disso está no fato de que: a escolha de uma aresta para a passagem do fluxo corresponde a um match entre cavalo e cavaleiro, sendo assim com o fluxo máximo representa o número máximo de arestas que eu consigo usar (cada aresta tem capacidade 1) para atribuir um cavaleiro a um cavalo.
Para usarmos o algoritmo clássico (Ford–Fulkerson) de fluxo máximo, nosso grafo tem que ter apenas um source e um sink. Para transformar um grafo com múltiplos sources em um grafo com apenas um, basta incluir um vértice extra no grafo e liga-lo a cada source, sendo que cada aresta adicionada tem um peso igual a capacidade do vértice (source). Analogamente, podemos usar essa mesma técnica para reduzir o número de sinks para um.
O número máximo de cavaleiros que poderiam ter um cavalo para montar pode ser calculado como o fluxo máximo que pode passar por esse grafo, considerando-se os cavaleiros como sources e os cavalos como sinks. A ideia por traz disso está no fato de que: a escolha de uma aresta para a passagem do fluxo corresponde a um match entre cavalo e cavaleiro, sendo assim com o fluxo máximo representa o número máximo de arestas que eu consigo usar (cada aresta tem capacidade 1) para atribuir um cavaleiro a um cavalo.
Para usarmos o algoritmo clássico (Ford–Fulkerson) de fluxo máximo, nosso grafo tem que ter apenas um source e um sink. Para transformar um grafo com múltiplos sources em um grafo com apenas um, basta incluir um vértice extra no grafo e liga-lo a cada source, sendo que cada aresta adicionada tem um peso igual a capacidade do vértice (source). Analogamente, podemos usar essa mesma técnica para reduzir o número de sinks para um.
Nenhum comentário:
Postar um comentário