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