Roteiro 6

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

< Voltar para: Roteiros | Roteiro 5

Introdução

Neste roteiro, estudaremos dois problemas em grafos fundamentais, tanto em aplicações gerais em Ciência da Computação quanto na Maratona de Programação: Caminho Mínimo e Árvore Geradora Mínima (AGM). O problema do Caminho Mínimo consiste em encontrar um caminho de menor custo entre vértices de um grafo onde as arestas têm peso. Já o problema da AGM pede que se construa uma árvore com arestas de um determinado grafo, mantendo a propriedade de que o grafo resultante deve ser conexo e a soma dos pesos das arestas na árvore deve ser a mínima possível.

Em competições, é comum que apareçam problemas de Caminho Mínimo ou AGM com modificações bem criativas. Neste roteiro estudaremos, principalmente, os problemas em sua forma mais pura, mas os problemas mais difíceis também cobrarão um pouco de criatividade.

Materiais de apoio

Problemas

Lista de problemas para serem resolvidos. A solução está disponível, mas recomendamos que não a consulte antes de sofrer um pouco com o problema. Os problemas em negrito são os mais importantes e mais difíceis. Faça-os antes de prosseguir para o próximo roteiro. As questões em rosa são para aquecimento (e bem interessantes!).

Roteiro 6
# Problema Link Online Judge Nível Observações
1 CONTAGEM Não é mais um Joguinho Canadense SPOJ-BR 2 -
2 ENGARRAF Engarrafamento SPOJ-BR 2 -
3 DESVIO Desvio de rota SPOJ-BR 2 -
4 REDOTICA Rede ótica SPOJ-BR 2 -
5 PONTES09 Caminho das pontes SPOJ-BR 2 -
6 INTERLMG Interligando a Sildávia SPOJ-BR 2 dica
7 MINIMO Final Mundial de 2008 SPOJ-BR 3 leia o Cormen!
8 MICEMAZE Mice and Maze SPOJ 2 -
9 CLEANRBT Cleaning Robot SPOJ 3 o número de células sujas é bem pequeno
10 MLASERP Laser Phones SPOJ 3 seja criativo para montar o grafo apropriado

Próximo roteiro

O próximo roteiro de treinamento tratará de problemas ad hoc simples. Recomendamos que você avance apenas depois de ler todo o material de apoio e ter feito, pelo menos, 6 problemas incluindo os 2 em negrito.

Link para o Roteiro 7

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas