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

Se da o retea de transport sub forma unui graf orientat cu $N$ noduri si $M$ arce. Fiecare arc are asociata o capacitate si un cost pentru fiecare unitate de flux ce trece pe arcul respectiv. Notam cu $S$ si $D$ sursa si respectiv destinatia din reteaua de transport considerata. Sa se determine costul minim pentru a se transmite o cantitate maxima de flux de la sursa la destinatie.

Se da o retea de transport sub forma unui graf orientat cu $N$ noduri si $M$ arce. Fiecare arc are asociate o capacitate si un cost pentru fiecare unitate de flux. In graf se afla $2$ noduri distincte, notate cu $S$ si $D$, ce reprezinta sursa si, respectiv, destinatia retelei. Sa se determine costul minim pentru a se transmite o cantitate maxima de flux de la sursa la destinatie.

h2. Date de intrare

Pe prima linie a fisierului de intrare $fmcm.in$, se afla $4$ numere intregi $N M S D$ cu semnificatia din enunt. Pe fiecare din urmatoarele $M$ linii se afla cate $4$ numere $x y c z$, reprezentand un arc de la $x$ la $y$ cu capacitatea $c$ si costul $z$.

Pe prima linie a fisierului de intrare $fmcm.in$, se afla $4$ numere intregi $N M S D$ cu semnificatia din enunt. Pe urmatoarele $M$ linii se afla cate $4$ numere $x y c z$, fiecare astfel de grup reprezentand un arc de la $x$ la $y$ cu capacitatea $c$ si costul $z$.

h2. Date de ieşire

* $1 ≤ M ≤ 12 500$
* $1 ≤ c ≤ 10 000$
* $-1 000 ≤ z ≤ 1 000$

* Se garanteaza ca graful nu va avea cicluri negative
* Se garanteaza ca nu exista nici un arc care sa intre in $S$ si nici un arc care sa iasa din $D$
* Intre oricare doua noduri $x$ si $y$ exista maxim un arc. In plus, daca exista arc intre $x$ si $y$ nu va exista arc intre $y$ si $x$

* Se garanteaza ca graful nu va avea cicluri negative.
* Se garanteaza ca nu exista nici un arc care sa intre in $S$ si nici un arc care sa iasa din $D$.
* Pentru simplitate, vom considera ca daca exista arc de la $x$ la $y$, atunci el este unic si nu va exista arc de la $y$ la $x$.

* Pentru $50%$ din teste $N ≤ 50$ si $M ≤ 200$

* Pentru $70%$ din teste $N ≤ 200$ si $M ≤ 7 500$

* Pentru $70%$ din teste $N ≤ 300$ si $M ≤ 10 000$

h2. Exemplu
table(example). |_. fmcm.in |_. fmcm.out |

| 5 7 2 5
3 1 7 -1
1 4 3 0
3 4 3 -4
1 5 7 0
4 5 1 1
2 5 8 -3
2 3 4 -3
| -42

| 5 7 1 5
1 2 9 5
1 3 2 4
2 3 3 3
2 4 2 1
3 4 2 2
3 5 10 7
4 5 3 4
| 86

|
h2. Indicatii de rezolvare

Aceasta problema se rezolva in mod asemanator cu problema determinarii 'fluxului maxim':problema/maxflow, cu cateva modificari. Este din nou necesara constuirea _grafului rezidual_, care contine toate arcele din graful initial si, in plus, toate {_arcele de intoarcere_}. Astfel, pentru fiecare arc {$x->y$} de cost $z$ din graful initial se adauga in graful rezidual arcul y->x cu capacitatea $0$ si costul {$-z$}. Algoritmul ruleaza atat timp cat se mai poate introduce flux in retea. La fiecare pas, este necesara gasirea unui _drum de ameliorare_ de cost minim de la sursa la destinatie. Apoi, fluxul va fi incrementat pe acest drum cu valoarea maxima posibila (minimul diferentelor dintre capacitate si flux pentru fiecare arc de pe drum). Pentru a gasi drumul de ameliorare optim din punct de vedere al costului putem folosi un algoritm de drum minim care sa permita existenta costurilor negative pe arce (costurile arcelor de intoarcere), precum "Bellman-Ford":http://en.wikipedia.org/wiki/Bellman_Ford. Algoritmul Bellman-Ford are complexitate $O(N*M)$, ceea ce conduce la o complexitate teoretica $O(N^2^*M^2^)$, insa in practica se comporta mai bine. Aceasta solutie obtine $50$ de puncte. O sursa pe aceasta idee poate fi gasita 'aici':job_detail/238401?action=view-source. Algoritmul Bellman-Ford poate fi rafinat folosind o coada pentru a mentine nodurile ce mai pot contribui la imbunatatirea costurilor. Desi complexitatea ramane aceeasi, in practica timpul de rulare scade simtitor. O astfel de abordare obtine $70$ de puncte. O sursa demonstrativa poate fi gasita 'aici':job_detail/238402?action=view-source.

Aceasta problema se rezolva in mod asemanator cu problema determinarii 'fluxului maxim':problema/maxflow, cu cateva modificari. Este din nou necesara constuirea _grafului rezidual_, in felul urmator: pentru fiecare arc din graful initial se mai adauga cate un arc (arc de intoarcere) orientat invers cu capacitatea $0$ si cu costul opus ({$-z$}). Algoritmul ruleaza atat timp cat se mai poate introduce flux in retea. La fiecare pas, este necesara gasirea unui drum de cost minim vaid (fluxul de pe fiecare arc sa fie strict mai mic decat capacitatea) de la sursa la destinatie numit _drum de augmentare_. Apoi, fluxul va fi incrementat pe acest drum cu valoarea maxima posibila (minimul din diferentele dintre capacitate si flux pentru fiecare muchie de pe drum). Pentru a gasi drumul de augmentare, o alternativa ar fi sa folosim algoritmul "Bellman-Ford":http://en.wikipedia.org/wiki/Bellman_Ford, datorita prezentei costurilor negative pe arce. Chiar daca $z ≥ 0$, arcele de intoarcere ar fi tot negative, deci si cu aceasta restrictie drumul de augmentare ar trebui cautat tot cu algoritmul Bellman-Ford. Acest algoritm are complexitate $O(N*M)$, ceea ce conduce la o complexitate totala $O(N^2^*M^2^)$, insa in practica se comporta mai bine. Aceasta solutie obtine $50$ de puncte; o sursa ce implementeaza aceasta idee poate fi gasita 'aici':job_detail/238401?action=view-source. Algoritmul Bellman-Ford poate fi rafinat folosind o coada pentru a mentine nodurile ce mai pot contribui la imbunatatirea costurilor. Desi complexitatea ramane aceeasi, in practica, timpul de rulare scade simtitor. O astfel de abordare obtine $70$ de puncte si o sursa demonstrativa poate fi gasita 'aici':job_detail/238402?action=view-source.

Pentru a imbunatati algoritmul de mai sus, atunci cand cautam drumul de ameliorare de cost minim putem folosi si 'algoritmul lui Dijkstra':problema/dijkstra, dar inainte graful trebuie modificat astfel incat sa nu mai exista arce cu cost negativ. Definim $Dist{~i~}$ ca fiind distanta minima de la $S$ la nodul $i$. Initial, folosind algoritmul lui Bellman-Ford, calculam valorile vectorului $Dist$. Apoi, fiecarui arc {$x->y$} de cost $z$ i se va asocia costul $z + Dist{~x~} - Dist{~y~}$. Costul arcelor devine pozitiv, altfel ar insemna ca $Dist{~x~} + z < Dist{~y~}$, ceea ce ar contrazice minimalitatea lui $Dist{~y~}$. Costul drumurilor minime difera fata de cele initale printr-o constanta, deci transformarea modifica doar costul acestora si nu le schimba cu alte drumuri. In consecinta, la fiecare pas vom putea folosi algorimul lui Dijkstra pentru a determina drumul de ameliorare si vom putea folosi distantele calculate cu acest algoritm pentru a modifica din nou costurile arcelor. Algoritmul lui Dijkstra are complexitate $O(M*logN)$, deci complexitatea totala devine $O(N*M^2^*logN)$, dar este iarasi supraestimata. Aceasta rezolvare obtine $100$ de puncte, iar o sursa demonstrativa se gaseste 'aici':job_detail/245450?action=view-source.

Pentru a gasi drumul de augmentare, poate fi folosit si 'algoritmul lui Dijkstra':problema/dijkstra, dar inainte graful trebuie modificat astfel incat sa nu mai exista arce cu cost negativ. Definim $Dist[i]$ distanta minima de la $S$ la nodul $i$. Initial, folosind algoritmul lui Bellman-Ford calculam $dist[i]$. Apoi costul fiecarui arc $z[x-y]$ va fi inlocuit cu $z[x->y] + Dist[x] - Dist[y]$. Costul arcelor devine pozitiv, altfel ar insemna ca $Dist[x] + z[x->y] < Dist[y]$, ceea ce ar contrazice minimalitatea lui $Dist[y]$. Costul drumurilor minime difera fata de cele initale prin constanta $Dist[x]-Dist[y]$, deci transformarea nu schimba drumul minim. Apoi, la fiecare pas vom putea folosi algorimul lui Dijkstra pentru a determina drumul de augmentare si vom putea folosi distantele calculate cu acest algoritm pentru a modifica din nou costurile arcelor. Algoritmul lui Dijkstra are complexitate $O(MlogN)$ si complexitatea totala este O(N*M^2^*logN), din nou supraestimata. Aceasta rezolvare obtine $100$ de puncte si o sursa ce foloseste aceasta idee se afla 'aici':.

h2. Aplicatii

Algoritmul de flux maxim si cost minim poate fi aplicat si pentru grafuri neorientate cu modificari minime. In plus, poate fi aplicat si pentru determinarea cuplajului de cost minim intr-un graf bipartit. De asemenea, putem determina si cuplajul de cost maxim intr-un graf biparit, folosind acelasi algoritm dupa ce costul fiecarei muchii a fost inlocuit cu diferenta dintre valoarea maxima a unei muchii si valoarea curenta. In acest caz, rezultatul va fi egal cu diferenta dintre produsul fluxului si valoarea maxima a unei muchii si costul fluxului obtinut pe graful modificat.
Rezolvarea urmatoarelor probleme foloseste ideile de mai sus:

Pentru a determina cuplajul de cost minim intr-un graf bipartit se foloseste acelasi algoritm ca cel prezentat in aceasta problema. De asemenea, pentru a determina cuplajul de cost maxim intr-un graf biparit, folosim acelasi algoritm dupa ce costul fiecarei muchii a fost inlocuit diferenta dintre valoarea maxima a unei muchii si valoarea curenta. In acest caz, rezultatul va fi egal cu diferenta dintre produsul fluxului si valoarea maxima a unei muchii si costul fluxului obtinut pe graful modificat. Algoritmul prezentat in aceasta problema este necesar pentru a rezolva mai multe probleme de informatica, cum ar fi:

* 'Cc':problema/cc
* 'Traseu':problema/traseu
* 'Renovare':problema/renovare
* 'Smen':problema/smen
* 'Adapost':problema/adapost

* 'Atac2':problema/atac2
== include(page="template/taskfooter" task_id="fmcm") ==

== include(page="template/taskfooter" task_id="fmcm") ==
 

3570