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 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.
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 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.
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 ≤ z ≤ 100
- 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 muchie de la x la y, atunci ea e unica si nu va exista muchie de la y la x.
Exemplu
| fmcm.in | fmcm.out |
|---|---|
| 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 |
Indicatii de rezolvare
Aceasta problema se rezolva in mod asemanator cu problema determinarii fluxului maxim, cu cateva modificari. Pentru fiecare arc din graf se mai adauga cate un arc (arc de intoarcere) orientat invers cu capacitatea 0 si cu costul opus celui initial (-z). Pe acest graf se pune problema gasirii unor drumuri de cost minim de la sursa la destinatie, care sa respecte conditiile unui graf rezidual. O prima idee ar fi folosirea algoritmului Bellman-Ford, datorita costurilor negative ce apar pe arcele de intoarcere. Astfel complexitatea totala este O(N2*M*B), unde B este o limita superioara a capacitatii totale a unui nod. O solutie folosind o implementare naiva a algoritmului Bellman-Ford obtine 50 de puncte. O data cu rafinarea implementarii algoritmului Bellman-Ford, folosind o coada pentru a mentine nodurile ce au potential pentru micsorarea distantei, viteza de rulare se imbunatateste simtitor. O astfel de implementare obtine in jur de 70 de puncte.
Aplicatii
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:
