Aluno: Marcos Massayuki Kawakami

Supervisor: José Coelho de Pina

O tema de fluxos em rede é recorrente em competições de programação. No entanto, a quantidade de material em português sobre o tema é excassa e raramente aborda tanto a parte teórica quanto a parte prática do assunto. Este trabalho tem como objetivo amenizar este problema, servindo de material didático sobre fluxos em rede para os interessados sobre o tema, com ênfase na resolução de problemas de programação competitiva. São apresentados a teoria elementar sobre o tema, algoritmos e suas respectivas implementações, bem como aplicações e extensões do problema do fluxo máximo e resoluções de problemas de competições passadas.

Motivação

Problemas cuja solução envolve o uso de algoritmos de fluxo em rede são recorrentes em competições de programação esportiva. Devido à sua complexidade, não são tão frequentes quanto problemas que envolvem algoritmos mais simples. No entanto, seu conhecimento é essencial para aqueles que buscam bons desempenhos nessas provas.

O estudo deste tema é, porém, muitas vezes prejudicado devido à escassez de material em língua portuguesa sobre o assunto com ênfase em competições de programação. Os materiais normalmente omitem uma implementação completa, prática e eficiente dos algoritmos, ou não abordam suas mais variadas aplicações. Assim, o estudo deste tema passa a depender fortemente da passagem de conhecimento de competidores mais experientes, reduzindo sua acessibilidade.

Por este motivo, este trabalho tem como principal objetivo servir de material de estudo de fácil acesso para todos que têm interesse em se aprofundar no tema de fluxo em rede e nas suas aplicações na resolução em problemas no estilo da Maratona de Programação (ACM-ICPC).

Objetivos

Este trabalho tem os seguintes objetivos:

• Estudar os algoritmos tradicionais usados na resolução dos problemas de Fluxo Máximo, Fluxo de Custo Mínimo, Circulação, dentre outros;
• Implementar os algoritmos mencionados acima de forma que o código fique sucinto e seja facilmente adaptável;
• Estudar a viabilidade do uso de algoritmos mais sofisticados durante competições de programação;
• Pesquisar e listar as diversas aplicações destes algoritmos na resolução de problemas, bem como exemplos de problemas de competições passadas;
• Elaborar um material didático baseado nos itens acima.

Atividade	Abr	Mai	Jun	Jul	Ago	Set	Out	Nov
Estudo e implementação dos algoritmos	•	•	•
Estudo de algoritmos mais sofisticados			•	•	•	•
Pesquisa de aplicações						•	•
Elaboração de textos			•	•	•	•	•	•