h2. Indicaţii de rezolvare
Pentru a rezolva aceasta problema putem folosi algoritmul "Edmonds-Karp":http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm. Acest algoritm introduce insa o notiune noua, anume aceea de {_graf rezidual_}. Graful rezidual este graful retelei de transport, in care pentru fiecare muchie introducem si muchia inversa, cu capacitate $0$. La fiecare pas trebuie sa gasim in acest graf un drum de la sursa la destinatie, in care fiecare muchie de pe drum sa aiba fluxul asociat pana in acest moment strict mai mic decat capacitatea sa. Putem face acest lucru usor, folosind un algoritm de parcurgere a grafurilor precum 'BFS':problema/bfs sau 'DFS':problema/dfs. Drumul astfel gasit se va numi {_drum de ameliorare_}. Dupa acest pas, calculam valoarea cu care putem mari fluxul pe acest drum, aceasta fiind valoarea minima cu care poate fi marit fluxul asociat fiecarei muchii care se afla pe drumul gasit. Odata gasita aceasta valoare, luam fiecare muchie $x -> y$ si marim fluxul pe aceasta muchie cu acea valoare, scazand de asemena tot aceasi valoare pe muchia $y -> x$. Astfel este posibil ca drumul nostru la un moment dat sa parcurga o muchie inversata, de capacitate $0$ si flux negativ, practic decrementand fluxul de pe muchia neinversata. Acest algoritm garanteaza ca in momentul in care nu vom mai gasi niciun drum de la sursa la destinatie in graful rezidual, atunci fluxul trimis prin retea este maxim. Complexitatea teoretica este {$O(N * M^2^)$}, insa in practica se comporta mult mai bine. Acest algoritm ar trebui sa obtina in jur de $70$ de puncte. O sursa pe aceasta idee se gaseste 'aici':job_detail/237100?action=view-source.

Pentru $100$ de puncte trebuie facuta o optimizare. Astfel, la fiecare pas construim arborele $BFS$ (excluzand destinatia), si acum un drum de la sursa la destinatie e reprezentat de un drum de la sursa (care este radacina arborelui) la o frunza legata de destinatie printr-o muchie nesaturata. Astfel putem la un pas sa marim fluxul pe un numar maximal de astfel de drumuri, fara a mai reface $BFS$-ul. Aceasta optimizare reduce destul de mult timpul de executie si obtine $100$ de puncte. O sursa care foloseste si aceasta optimizare se gaseste 'aici':job_detail/237099?action=view-source.
Pentru mai multe detalii puteti consulta si acest "articol":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow.

Exista si algoritmi mai buni pentru a rezolva aceasta problema, nefiind insa necesari la aceasta problema, cum ar fi "algoritmul lui Dinic":http://www.msri.org/about/computing/docs/magma/html/text1499.htm si "algoritmul lui Karzanov":http://deepblue.lib.umich.edu/handle/2027.42/30217.
h2. Aplicaţii