Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | fmcm.in, fmcm.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Flux maxim de cost minim
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.
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.
Date de ieşire
În fisierul de iesire fmcm.out se va afla un numar intreg reprezentand valoarea costului minim pentru a transmite o cantitate maxima de flux de la sursa la destinatie.
Restricţii
- 1 ≤ N ≤ 350
- 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
- Pentru 50% din teste N ≤ 50 si M ≤ 200
- Pentru 70% din teste N ≤ 200 si M ≤ 7 500
Exemplu
| 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 |
Indicatii de rezolvare
Aceasta problema se rezolva in mod asemanator cu problema determinarii fluxului maxim, 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. Algoritmul Bellman-Ford are complexitate O(N*M), ceea ce conduce la o complexitate teoretica O(N2*M2), insa in practica se comporta mai bine. Aceasta solutie obtine 50 de puncte. O sursa pe aceasta idee poate fi gasita aici. 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.
Pentru a imbunatati algoritmul de mai sus, atunci cand cautam drumul de ameliorare de cost minim putem folosi si algoritmul lui Dijkstra, dar inainte graful trebuie modificat astfel incat sa nu mai exista arce cu cost negativ. Definim Disti 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 + Distx - Disty. Costul arcelor devine pozitiv, altfel ar insemna ca Distx + z < Disty, ceea ce ar contrazice minimalitatea lui Disty. 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*M2*logN), dar este iarasi supraestimata. Aceasta rezolvare obtine 100 de puncte, iar o sursa demonstrativa se gaseste aici.
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:
