sexta-feira, 9 de agosto de 2013

Maratona de Programação - Grafos

Olá pessoal, nesse post irei dar algumas dicas sobre como resolver alguns problemas de Maratona de Programação envolvendo Grafos.

O site de onde foram tirados os problemas foi o site do URI Online Judge:

O primeiro problema que irei analisar é o problema Desenhando Labirintos.


O problema pede que você determine a quantidade mínima de movimentos que precisam ser feitos para desenhar o labirinto partindo de um nodo "x" e finalizando nesse mesmo nodo "x". Lembrando que NÃO é possível levantar a caneta do papel.

O problema tem como entrada o nodo de onde você deve partir, a quantidade de vértices e a quantidade de arestas. Por último também são dadas as ligações.

Para resolver esse problema basta fazer uma busca em profundidade (DFS). Pois a DFS ela parte de um nodo e explora tanto quanto possível cada um dos ramos antes de voltar. Você pode utilizar uma matriz de adjacência para representar o grafo. Trata-se de um grafo não direcionado, então quando você receber uma ligação, você adiciona a ida e a volta, exemplo:

ligação 2 3
mat[2][3] = 1;
mat[3][2] = 1;

Colocar 1 na matriz é a maneira de identificar que há uma ligação, o contrário seria colocar 0 indicando que não há ligação.

Na DFS você vai contar o número de arestas. Quando mat[v][i] (sendo 'v' o vértice por onde vai iniciar e 'i' variável de controle do 'for' por exemplo) for diferente de 0 e visitados[i] for falso, então você incrementa o número de aresta.

No final, você vai ter a quantidade de arestas da ida, mas o problema pede os movimentos de volta também, então é só multiplicar por 2 depois que você tiver o número de arestas contadas na busca em profundidade.

O próximo problema é considerado um pouco mais difícil, mas se você conhecer os algoritmos também se torna fácil, iremos analisar o problema  Ir e Vir que foi proposta na Maratona de 2010.


O problema pede que você verifique um determinado requisito de conectividade do grafo.

Esse requisito é: dadas duas intersecções V e W, deve ser possível viajar de V para W e de W para V. Você tem que determinar se esse requisito é satisfeito ou não.

Quando eu resolvi esse problema eu utilizei lista de adjacências para representar o grafo. Nesse problema temos um grafo direcionado. Se você usar uma DFS normal como utilizamos no problema anterior não vai passar, porque você tem que verificar se o grafo é fortemente conectado (dica: algoritmo de Tarjan), ou seja, tem que verificar se um grafo direcionado é conectado.

Se você conseguir verificar se um grafo direcionado é conectado, então você irá resolver esse problema facilmente.

O próximo problema que irei falar é mais fácil do que o anterior. É o problema das Estradas Escuras, segue o link:


Nesse problema temos um grafo com pesos. O número de vértices que no problema é chamado de 'm' pode chegar até 200000. Se você tentar alocar isso numa matriz normal não irá conseguir, são muitos vértices. 

Você consegue facilmente guardar numa variável a soma de todos os custos. Pois bem, o problema quer o máximo valor diário que o governo pode economizar. Uma das formas de resolver esse problema é utilizar Kruskal, porque vai te retornar o custo total da árvore geradora mínima. Tendo esse custo, então é só calcular a diferença entre a soma de todos os custos com o custo retornado pelo algoritmo.

O próximo problema que iremos falar é o problema chamado Países em Guerra.

Link no URI: http://www.urionlinejudge.com.br/judge/problems/view/1148
Link no SPOJ: http://br.spoj.com/problems/PAISES/

Nesse problema você irá utilizar Dijkstra para calcular o menor custo indo de uma cidade a outra. Cada caso de teste possui várias consultas para saber o tempo mínimo de horas (custo) para enviar uma carta.

Atenção para o detalhe: uma carta pode ser enviada por meio eletrônico, ou seja, sem custo algum. Isso irá ocorrer se as agências estiverem no mesmo país e duas agências estão no mesmo país se houver uma forma de uma carta impressa enviada de uma das agências ser entregue na outra agência. Esse detalhe é muito importante para resolver o problema!

Com o algoritmo de Dijkstra você resolve facilmente o problema, mas tem que ficar atento em como usá-lo e ter atenção também para o detalhe comentado anteriormente.

Quando resolvi o problema eu fiz o seguinte: eu tenho uma variável INFINITO cujo valor dela está acima do limite do peso do problema. O limite do peso do problema é 1000, pois o H só pode chegar no máximo a 1000, ou seja, 1000 é o limite máximo do peso (custo).

Eu utilizei matriz de adjacência para resolver esse problema, lembrando que a matriz tem que ter um tamanho máximo acima de 500, pois N pode chegar a 500. Eu inicializei essa matriz com o valor de INFINITO (exemplo: 10000, pois 10000 é maior que 1000, poderia utilizar só 1001 por exemplo para economizar espaço).

Logo após pegar cada X, Y e H, eu verifico se mat[Y - 1][X - 1] (utilizei -1 porque o índice da matriz começa do 0) é diferente de INFINITO (valor que eu inicializei a matriz). Se for diferente de INFINITO então eu coloco 0 tanto em mat[X - 1][Y - 1] como também em mat[Y - 1][X - 1], ou seja, esse é o caso da mesma cidade, ou seja, a entrega das cartas terá custo 0. Senão (se for igual a INFINITO) eu faço a ligação somente da ida, ou seja, coloco H em mat[X - 1][Y - 1].

Depois é só ler as consultas, no meu algoritmo eu tinha uma variável que contava a quantidade de nós que foram percorridos, essa variável chamei de cam_qtd. Então eu pegava o resultado de Dijkstra, se cam_qtd fosse igual a 0, então é porque não existia caminho da cidade O a D, então mostrava a mensagem 'Nao e possivel entregar a carta'. Senão, imprimia o resultado retornado pelo algoritmo de Dijkstra.

Espero que as dicas sejam úteis, analisem os problemas, qualquer crítica ou sugestão é só deixar nos comentários.


Nenhum comentário: