Solução Pontes de São Petesburgo

0 Flares Facebook 0 0 Flares ×

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:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: