* $2 ≤ N ≤ 1 000$
* $1 ≤ M ≤ 5 000$
* Nodul $1$ este nodul sursa, iar nodul $N$ este nodul destinatie

* Pentru fiecare muchie, capacitatea va fi un numar natural in intervalul {$[..., ...]$}

* Pentru fiecare muchie, capacitatea va fi un numar natural in intervalul {$[1, 110 000]$}

h2. Exemplu

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. Aplicatii