Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-12-30 20:31:34.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:fmcm.in, fmcm.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.3 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

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.infmcm.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. 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 ameliorare. 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 ameliorare, o alternativa ar fi sa folosim algoritmul Bellman-Ford, datorita prezentei costurilor negative pe arce. Acest algoritm are complexitate O(N*M), ceea ce conduce la o complexitate totala O(N2*M2), insa in practica se comporta mai bine. Aceasta solutie obtine 50 de puncte; o sursa ce implementeaza 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 aproximativ 70 de puncte si o sursa demonstrativa poate fi gasita aici.

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:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?