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:


#include <cstdio> // scanf e printf
#include <cstring> // memset
#define MAXR 110 // número máximo de regiões
#define MAXK 10100 // número máximo de pontes
int r, k, inc[110], tab[110][10100]; // declaração de variáveis
bool controle;
bool possivel(int davez, int qtd){ // função recursiva da dp
// se já achei uma solução, então pronto, retorne a função
if(controle==true) return true;
// se a função já foi calculada para estes parâmetros, retorne o valor que temos salvo
if(tab[davez][qtd]>=0) return tab[davez][qtd];
// se davez>r, já testamos todas as regiões e ainda não encontramos um jeito, retorne false
if(davez>r) return tab[davez][qtd]=false;
// se qtd=k, então acabamos de achar um conjunto que é exemplo do que o problema pede, retorne true
if(qtd==k) return tab[davez][qtd]=controle=true;
// se qtd>k, já estouramos a cota de pontes e esse conjunto irá atingir mais que k pontes
if(qtd>k) return tab[davez][qtd]=false;
// chamamos a recursão: vemos se é possível ter k pontes colocando ou não a próxima região
if(possivel(davez+1, qtd+inc[davez+1]) || possivel(davez+1, qtd)) return tab[davez][qtd]=controle=true;
// se o programa chegou aqui, então o "if" de cima não retornou e não foi possível achar as k pontes
return tab[davez][qtd]=false;
}
// perceba como a função sempre atualiza os valores salvos na tabela de pd e na variável controle
int main(){
while(scanf("%d %d", &r, &k)!=EOF){ // lemos os vários casos de teste da entrada
memset(inc, 0, sizeof(inc)); // zeramos o número de pontes que incide em cada região
memset(tab, -1, sizeof(tab)); // colocamos -1 em todos os valores da tabela de pd
controle=false; // dizemos que ainda não encontramos solução
int r1, r2;
for(int i=0; i<k; i++){
scanf("%d %d", &r1, &r2); // lemos as pontes da entrada
// e adicionamos 1 unidade na incidência de pontes das cidades nas duas extremiades da ponte
inc[r1]++;
inc[r2]++;
}
// se a função retornar true, imprimimos 'S', caso contrário, imprimimos 'N'
printf("%c\n", possivel(0, 0) ? 'S':'N');
}
return 0;
}

view raw

pontes.cpp

hosted with ❤ by GitHub