== include(page="template/taskheader" task_id="maxflow") ==

O retea de transport este un graf orientat in care fiecare muchie are asociata o anumita capacitate si o anumita cantitatea de flux. Fluxul primit de fiecare muchie trebuie sa fie mai mic sau egal decat capacitatea acesteia. De asemenea pentru fiecare nod fluxul care intra in nod trebuie sa fie egal cu fluxul care iesa. Cu alte cuvinte, suma fluxulurilor asociate muchiilor care intra intr-un nod trebuie sa fie egala cu suma fluxurilor asociate muchiilor care iesa din nod, exceptie facand nodurile speciale $S$ si $D$, denumite sursa respectiv destinatie. Din sursa poate iesi flux fara sa intre iar in destinatie poate intra flux fara sa iasa. Valoarea fluxului unei astfel retele este egal cu suma fluxului care iesa din sursa sau suma fluxului care intra in destinatie.

O retea de transport este un graf orientat in care fiecare muchie are asociata o anumita capacitate si o anumita cantitate de flux. Fluxul primit de fiecare muchie trebuie sa fie mai mic sau egal decat capacitatea acesteia. De asemenea pentru fiecare nod fluxul care intra in nod trebuie sa fie egal cu fluxul care iese. Cu alte cuvinte, suma fluxulurilor asociate muchiilor care intra intr-un nod trebuie sa fie egala cu suma fluxurilor asociate muchiilor care ies din nod, exceptie facand nodurile speciale $S$ si $D$, denumite sursa, respectiv destinatie. Din sursa poate iesi flux fara sa intre iar in destinatie poate intra flux fara sa iasa. Valoarea fluxului unei astfel retele este egal cu suma fluxului care iese din sursa sau suma fluxului care intra in destinatie (se poate demonstra ca cele doua fluxuri sunt egale).

h2. Cerinta

Dandu-se o retea de transport, in care initial fluxul pe fiecare muchie este 0, sa se calculeze fluxul maxim care poate fi trimis prin aceasta.

Dandu-se o retea de transport, in care initial fluxul pe fiecare muchie este {$0$}, sa se calculeze fluxul maxim care poate fi trimis prin aceasta.

h2. Date de intrare

Fisierul de intrare $maxflow.in$ va contine pe prima linie $2$ numere, $N$ si $M$, reprezentand numarul de noduri respectiv numarul de muchii. Pe urmatoarele $M$ linii se vor afla cate $3$ numere, $x$, $y$ si $z$ insemnand ca exista o muchie care pleaca de la nodul $x$, ajunge in nodul $y$ si are capacitatea $z$.

Fisierul de intrare $maxflow.in$ va contine pe prima linie $2$ numere, $N$ si $M$, reprezentand numarul de noduri si numarul de muchii din retea. Pe fiecare din urmatoarele $M$ linii se vor afla cate $3$ numere naturale, $x$, $y$ si $z$, cu semnificatia ca exista o muchie care pleaca de la nodul $x$, ajunge in nodul $y$ si are capacitatea $z$.

h2. Date de ieşire

 
In fisierul de iesire $maxflow.out$ se va afla un singur numar $F$ reprezentand fluxul maxim ce poate fi trimis prin retea.

In fisierul de iesire $maxflow.out$ se va afla un singur numar $F$, reprezentand fluxul maxim ce poate fi trimis prin retea.

h2. Restricţii
* $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 {$[..., ...]$}

h2. Exemplu

In figura de mai sus, fiecare muchie are asociate $2$ numere reprezentand fluxul si capacitatea asociate muchiei respective.

h2. Indicatii 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, si anume notiunea 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 o sa vrem 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 cautare gen 'BFS':problema/bfs sau 'DFS':problema/dfs. Dupa ce am gasit acest drum, 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 valore, 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 inversa, de capacitate $0$ si flux negativ, practic scotand flux de pe aceasta muchie. Acest algoritm garanteaza ca in momentul in care nu vom mai gasi nici un astfel de drum 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 care se bazeaza pe aceasta idee se afla '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 aduce $100$ de puncte.
O sursa care foloseste si aceasta optimizare se gaseste 'aici':job_detail/237099?action=view-source

h2. Indicaţii de rezolvare

Pentru mai multe detalii puteti consulta acest "articol":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow.

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, si anume notiunea 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 valore, 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 inversa, de capacitate $0$ si flux negativ, practic scotand flux de pe aceasta muchie. Acest algoritm garanteaza ca in momentul in care nu vom mai gasi nici un astfel de drum 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.

h2. Aplicatii