Răspuns: 033 Flux maxim de cost minim

[•stef2n]

Am o mare problema la care ma gandesc de 2 saptamani... Nu reusesc sa pricep cum sa construiesc costurile pentru o retea de transport in care se cere fluxul maxim de cost minim. In cartea "Informatica pentru grupele de performanta" este foarte ambiguu: "In unele situatii exista posibilitatea asocierii unor costuri pentru arcele grafului (pe langa capacitati). In aceasta situatie va trebui sa determinam un flux maxim de cost minim. [...] Pentru a determina un astfel de cost minim este suficient sa folosim o varianta a algoritmului Ford-Fulkerson in cadrul careia sa determinam la fiecare pas drumuri de crestere de cost minim."
Se pot pune mai multe intrebari:
1. Cum este definita functia de cost (este cost pe arc sau este un cost unitar in functie de valoarea fluxului pe acel arc)
2. Drumurile de crestere, se spune dupa o pagina, se determina cu Bellman-Ford. In aceasta situatie inseamna ca o sa apara si costuri negative.
    A doua intrebare este: Cum se modifica costul pe arce in momentul in care "bag" flux pe un drum de crestere?
P.S. Algoritmul Ford-Fulkerson pe care il stiu eu e cu determinarea drumurilor de crestere si modificarea capacitatilor arcelor din drum, adaugand sau scazand valoarea fluxului pe acel drum