Roteiro 13 - DCC UFMG - Maratona de Programação
< Voltar para: Roteiros | Roteiro 12
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.
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.
Tutorial do TopCoder
O algoritmo de fluxo máximo geral
O algoritmo de Edmonds-Karp
Lista de problemas para serem resolvidos. A solução está disponível, mas recomendamos que não a consulte antes de muito esforço.
MTOTALF Total Flow SPOJ 2
UVa 820 Internet Bandwidth UVa 2
CAVALOS A lei vai a Cavalo! SPOJ-BR 3
HOOLIGAN Hooligans SPOJ-BR 3
OLIMP Olimpíadas SPOJ-BR 4
DISJPATH Disjoint Paths SPOJ 3
IM Intergalactic Map SPOJ 3
UVa 10480 Sabotage UVa 3
UVa 10349 Antenna Placement UVa 3
UVa 11506 Angry Programmer UVa 3
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.