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 , de , e depois o número de pontes que incide em cada região será salvo no vetor . Toda vez que lermos uma ponte de A para B, aumentaremos e em uma unidade.
Testar todas as possibilidades significa testar todos os possíveis conjuntos de regiões. Para isso, vamos criar uma função que recebe como entrada dois inteiros: o que representa qual região eu estou checando se vou colocar ou não no conjunto que estou testando, e o , 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 , 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 já tiver superado o valor de , já é impossível que tal conjunto dê certo, pois só iremos adicionar mais regiões e o valor de só irá crescer. Se em algum momento o valor de for igual ao de , 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 . Para verificar se é possível colocando a próxima região, adicionamos o número de pontes incidentes nela a e chamamos a função para essa região: . 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: . 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 || .
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 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 de dimensões por (onde é o valor máximo de e é o valor máximo de ). 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 então o valor de receberá o valor calculado ( se true e 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 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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |