Roteiro 13

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

< Voltar para: Roteiros | Roteiro 12

Introdução

Neste roteiro trataremos sobre um tópico muito abordado em competições: Fluxo Máximo e Corte Mínimo. Estes algoritmos sobre grafos possibilitam maximizar um conjunto requerido, casar conjuntos e minimizar custos sobre alguma propriedade. O algoritmo é bem simples, mas é muito bom entender seu funcionamento tanto quanto seu uso, o que é bem explicado em diversos materiais sobre teoria dos grafos.

Materiais de Apoio

O tutorial do TopCoder é o material que melhor explica o funcionamento do algoritmo, além de seu uso. O teorema exposto no artigo da wikipedia é também comentado em outros artigos. Por último são apresentados algoritmos em pseudo-linguagens de programação para facilitar sua implementação.

Problemas

Lista de problemas para serem resolvidos. A solução está disponível, mas recomendamos que não a consulte antes de muito esforço.

Roteiro 13
# Problema Link Online Judge Nível
1 MTOTALF Total Flow SPOJ 2
2 UVa 820 Internet Bandwidth UVa 2
3 CAVALOS A lei vai a Cavalo! SPOJ-BR 3
4 HOOLIGAN Hooligans SPOJ-BR 3
5 OLIMP Olimpíadas SPOJ-BR 4
6 DISJPATH Disjoint Paths SPOJ 3
7 IM Intergalactic Map SPOJ 3
8 UVa 10480 Sabotage UVa 3
9 UVa 10349 Antenna Placement UVa 3
10 UVa 11506 Angry Programmer UVa 3

Próximo Roteiro

O próximo roteiro de treinamento tratará de problemas em geometria computacional, sobre polígonos e círculos, além do algoritmo Convex Hull. 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 14

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas