Skip to content

Instantly share code, notes, and snippets.

@rogerioagjr
Last active August 29, 2015 14:19
Show Gist options
  • Save rogerioagjr/802793ec270c731ecc8e to your computer and use it in GitHub Desktop.
Save rogerioagjr/802793ec270c731ecc8e to your computer and use it in GitHub Desktop.
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment