Solução Pontes de São Petesburgo

Solução por Rogério Júnior

A solução deste problema envolve testar todas as possibilidades com uma função recursiva, de maneira eficiente através de programação dinâmica. Se você nunca ouviu falar disso,  clique aqui para ver a aula do Curso Noic de Informática sobre Programação Dinâmica.

Ao ler a entrada, guardaremos os valores de $$k$$, de $$r$$, e depois o número de pontes que incide em cada região será salvo no vetor $$inc$$. Toda vez que lermos uma ponte de A para B, aumentaremos $$inc[a]$$ e $$inc[B]$$ em uma unidade.

Testar todas as possibilidades significa testar todos os possíveis conjuntos de regiões. Para isso, vamos criar uma função $$possivel$$ que recebe como entrada dois inteiros: o $$davez$$ que representa qual região eu estou checando se vou colocar ou não no conjunto que estou testando, e o $$qtd$$, que representa quantas pontes já estão incidindo sobre o conjunto selecionado. Ela deve retornar true se for possível construir o exemplo pedido pelo problema e false se for impossível, partindo da região e da quantidade de pontes já incidente que a função recebe.

Para construir a função da pd, devemos fazer primeiro as bases, ou seja, quando a função para de chamar a recursão. Se estivermos olhando uma região maior que $$r$$, significa que já olhamos todas as regiões e ainda não foi possível, logo, não faz sentido continuar e a função deve retornar false. Além disso, se $$qtd$$ já tiver superado o valor de $$k$$, já é impossível que tal conjunto dê certo, pois só iremos adicionar mais regiões e o valor de $$qtd$$ só irá crescer. Se em algum momento o valor de $$qtd$$ for igual ao de $$k$$, então encontramos um conjunto que atende à necessidades do problema e a função deve retornar true.

Feito isso, chamaremos a recursão. A ideia é verificar se é possível chegar à quantidade de k pontes adicionando a próxima região ou não. Se for possível de alguma das duas maneiras, a função deve retornar true. Na prática, chamamos a função $$possivel(davez, qtd)$$. Para verificar se é possível colocando a próxima região, adicionamos o número de pontes incidentes nela a $$qtd$$ e chamamos a função para essa região: $$possivel(davez+1, qtd+inc[davez+1])$$. Verificar se é possível sem colocar a próxima região é análogo, apenas vamos chamar a função para ela sem adicionar a quantidade de pontes que incidem sobre ela: $$possivel(davez+1, qtd)$$. Lembre-se que se for possível em qualquer um dos casos, a função que as chamou deve retornar true, logo a recursão fica

return $$possivel(davez+1, qtd+inc[davez+1]) $$ || $$possivel(davez+1, qtd)$$.

Assim se chamarmos a função começando da região zero e com nenhuma ponte já incidente, a função testará, para cada região, se colocando-a ou não, é possível chegar à quantidade desejada de pontes, ou seja, devemos imprimir ‘S’ se a função $$possivel(0,0)$$ retornar true e ‘N’ caso contrário.

Ainda falta a armazenagem dos valores já calculados da função para evitar recálculo, que é a programação dinâmica. Essa é a parte mais simples: construímos uma matriz $$tab$$ de dimensões $$MAXR$$ por $$MAXK$$ (onde $$MAXR$$ é o valor máximo de $$r$$ e $$MAXK$$ é o valor máximo de $$k$$). No começo, todos o valores da matriz devem receber -1, que significa que ainda não sabemos nenhum valor da função. Quando calculamos $$possivel(i, j)$$ então o valor de $$tab[i][j]$$ receberá o valor calculado ($$1$$ se true e $$0$$ se false). Assim, toda vez que chamarmos a função, verificaremos se ela já foi calculada antes (se o valor salvo na matriz para os parâmetros chamados é positivo) e, se for, já retornamos logo esse valor.

Outra boa otimização é guardar uma variável $$controle$$ que começa falsa e diz se em algum momento já foi possível encontrar um conjunto que atende às especificações do problema. Se foi, não há para que continuar chamando a função, a resposta será ‘S’ de qualquer maneira. Enfim, vamos ao código: