033 Flux maxim de cost minim

[•pauldb]

Aici puteti discuta despre problema Flux maxim de cost minim din Arhiva educationala.

[•runnaway90]

 Ar fi utila si o sursa cu Roy-Floyd pentru determinarea drumului de cost minim.. nu e solutia cea mai eficienta insa pentru grafuri mici e cea mai rapid de implementat ..
 
 As mai vrea sa mentionez ca ar fi bine ca sursele oficiala as nu foloseasca STL sau macar sa fie si surse fara STL ... uneori exista situatii care creaza disconfort datorita faptului ca nu toti stim bine stl .. mai degraba bajbaim fara sa intelegem clar de ce merge cum merge + exista destule momente cand nu este utilizabil cum ar fi judeteana , concursuri interjudetene , programatorii pascal astfel incat surse fara stl necesita de cele mai multe ori mai multa finete in codare si ar merita niste surse scrise ca si model .

[•sima_cotizo]

Poate e mai avantajos cum spui tu, dar cred ca doar structurile de baza (care sunt implementate si in STL in mare parte si utilizate in sursele oficiale) ar trebui sa aiba atat "surse complete", cat si implementarea STL. La algoritmii care au la baza o alta structura de baza se poate folosi STL pt ca fiecare utilizator nu trebuie sa se concentreze asupra structurii, ci a algoritmului in sine (daca vrei e ca o scriere in pseudocod, unde ai "insereaza in heap" direct, nu un while).

[•razyelx]

Paul, in sursa "luni 29 decembrie 2008 02:50:46" sunt cateva secevnte care nu le inteleg. De ce in bellmanford() ai pus un while(!stop), si de ce returnezi Vmin * Dist[D] ?

[•marcelcodrea]

Pentru că în momentul în care stop rămâne 1 dupa iniţializarea de la începutul buclei, înseamnă că s-au obţinut distanţele minime, deoarece la pasul curent nu s-a actualizat nimic(stop nu a devenit 0).

Vmin * Dist[D] pentru că Vmin e fluxul maxim care poate fi trimis şi el trece din nod în nod cu diferite costuri pe unitatea de flux.
Sa presupunem ca drumul de distanţă minimă până la D e format din trei muchii cu costurile cost1, cost2, cost3. Când trimitem Vmin unităţi de flux vom avea Vmin * cost1 + Vmin * cost2 + Vmin * cost3, se da factor comun şi iese Vmin * (cost1 + cost 2 + cost3) care e tocmai Vmin * Dist[D].

[•Florian]

Cod:

 daca exista arc intre x si y nu va exista arc intre y si x 

Cum ar trebui rezolvata problema daca aceasta restrictie nu ar exista? 

[•pauldb]

Pentru fiecare arc creezi un arc de intoarcere. Dar atunci cand bagi flux pe un arc trebuie sa ai grija scazi fluxul pe arcul invers introdus de tine, nu pe celalalt. La fel procedezi si daca graful nu e orientat.

[•devilkind]

Ai putea sa tii 2 matrice. Una in care sa tii muchiile normale si una in care sa tii muchiile inverse. In felul cand bagi flux pe x -> y faci F[ x ][ y ]++, INV[ y ][ x ]--. In INV o sa tii muchiile inverse din graful rezidual practic.

[•tvlad]

[x] este un bullet patrat in BBCode, se poate scrie

Cod:

[nobbc][x][/nobbc]

[•ooctav]

Am observat ca unele surse iau 100 folosind dijkstra fara schimbarea costurilor pe noduri ...
E din cauza testelor sau se poate demonstra ca este corect ?

[•robigi]

salut, puteti sa va uitati va rog pe sursa asta: http://infoarena.ro/job_detail/477715?action=view-source

iau doar 20 de puncte cu incorect si stiu ca gresesc la calcularea costului final dar chiar nu ma prind de ce
fluxul maxim il obtin de fiecare data bine, am verificat cu sursa de la flux maximal cu toate testele si peste tot obtin raspunsul corect, dar nu calculez bine costul minim.   folosesc matricea ccost[j][k] = costul muchiei j-k, iar in antdef[j]=parintele/predecesorrul lui j si deoarece obtin bine fluxul maxim probabil ca este corect calculat antdef[]-ul, deci chiar nu ma prind ce poate fi gresit

[•blustudio]

Cred ca este o problema cu limita de timp, nici sursa oficiala nu scoate mai mult de 70p.

Modificare:
Sursa oficiala(70p): http://infoarena.ro/job_detail/661219
Am reusit acum sa obtin 100p, sursa este http://infoarena.ro/job_detail/661390

[•stefanzzz]

Nu vad de ce este necesara modificarea costurilor pt a fi toate pozitive. In cazul in care costurile raman asa cum sunt, singura diferenta ar fi ca la un pas valoarea din heap-ul Djikstra(ce ar fi,sa zicem, distanta pana la nodul x) ar putea fi mai mica decat valoarea de la pasul anterior(distanta pana la nodul y). Insa, cum nu exista cicluri de cost negativ, distanta minima pana la y nu ar putea fi modificata si deci algoritmul ar fi corect. Daca gresesc, corectati-ma va rog.

[•klamathix]

Nu vad de ce este necesara modificarea costurilor pt a fi toate pozitive. In cazul in care costurile raman asa cum sunt, singura diferenta ar fi ca la un pas valoarea din heap-ul Djikstra(ce ar fi,sa zicem, distanta pana la nodul x) ar putea fi mai mica decat valoarea de la pasul anterior(distanta pana la nodul y). Insa, cum nu exista cicluri de cost negativ, distanta minima pana la y nu ar putea fi modificata si deci algoritmul ar fi corect. Daca gresesc, corectati-ma va rog.

Din pacate, nu, Dijkstra nu merge daca exista arce de cost negativ. Principiul la Dijkstra e ca daca la un anumit pas nodul X este nodul cu distanta minima asociata pana acum, atunci sigur aceasta este distanta lui finala, fiindca altfel, ar trebui sa fie imbunatatit de un alt nod care are d[]-ul mai mare decat el. Ori daca exista arce cu cost negativ (e suficient arce, nu e nevoie de cicluri negative), costul lui X poate fi intr-adevar imbunatatit de un nod care in ordinea normala de Dijkstra s-ar expanda dupa el. Si asta inseamna ca tot ce ai calculat pe baza lui X nu mai este corect.

Uite aici un exemplu

Cod:

n = 4 , m = 4

1 -> 2 cost 6
1 -> 3 cost 8
3 -> 2 cost -3
3 -> 4 cost 1

Dijkstra-ul expandeaza sursa, nodul 1. Apoi expandeaza 2-ul fiindca are costul 6 iar nodul 3 are costul 8. Dupa care ajunge la 4, fiindca are costul 7 si e si el mai mic decat nodul 3. Si acum apare problema: 3 este expandat ultimul si imbunatateste costul lui 2, il face 5. Ceea ce inseamna ca si costul lui 4, bazat pe cel al lui 2 este gresit. Avand arce pozitive, asta nu se intampla niciodata, din motivele subliniate 

[•stefanzzz]

  Da, ai dreptate. Mersi pentru explicatie!

[•scipianus]

Se mai poate scoate 100pct cu limita actuala de timp? Sursa asta http://infoarena.ro/job_detail/744975 ia 70pct (variaza la ultimul test in jurul a 400ms si il prinde uneori,dar testul 8 ramane cu TLE).

Totusi,ma mai baga cineva in seama cand zic,din nou (am repostat mesajul de sus de vreo 3-4 ori pana acum), ca trebuie marit timpul la problema asta? Da,vad ca recent a luat cineva 100,dar in mare parte de cand s-au recalculat timpii,solutia cu Dijkstra ia 70 in loc de 100 si solutia cu Bellman Ford ia 50 in loc de 70
As aprecia daca un admin s-ar uita peste ce zic eu si ar decide sa mareasca timpul

[•klamathix]

Toti adminii sunt ocupati in ultima vreme si ne uitam pe infoarena, asa, intr-un fel de hover mode. Cand o sa avem timp o sa schimbam limita probabil.
Care e urgenta totusi?

[•scipianus]

Nu-i urgenta,dar prima data cand am postat asta a fost pe la inceputul verii si de atunci nu raspunsese cineva

[•wefgef]

Am marit limita la 0.6 secunde.

[•costyv87]

Imi poate spune si mie cineva care e optimizarea care sa-mi aduca 100 la problema asta ? Chiar nu imi dau seama   

Uitati aici sursa:

http://infoarena.ro/job_detail/914581

[•ctlin04]

Problema asta ma dispera!  
Nu pot gasi greseala nicidecum, iata sursa http://www.infoarena.ro/job_detail/999060. Cel mai ciudat e ca la mine pe calculator merg bine toate testele de la atasamente.  
Pls help. Ramin dator  

LE: Se pare ca ceva nu e bine cu coada. Programul meu baga incontinuu noduri si depaseste limita. Acest lucru se intimpla doar pe site pentru ca la mine ruleaza bine si la debug se vede clar ca nu introduc in coada mai multe elemente decit limita. E ceva in neregula cu evaluatorul sau este ceva special cu care nu m-am mai intilnit pina acum???

Le2: Am rezolvat in sfirsit. Greseala chiar ca a fost banala am inlocuit fin>>x>>y>>cap[ x ][y]>>cost[ x ][y] cu fin>>x>>y; fin>>cap[ x ][y]>>cost[ x ][y]; 

[•mouse_wireless]

Imi explica si mie cineva ceva la aceasta problema va rog?
Am luat 100 de puncte la ea, dar nu prea inteleg de ce functioneaza...

La inceput nu intelegeam de ce trebuiau ajustate costurile de fiecare data cand faci Dijkstra in loc sa le ajustezi o singura data cu Bellman-ul de la inceput, dar apoi mi-am dat seama ca tu vrei costurile minime luand in considerare doar muchiile nesaturate.. dar acum am o alta problema...

Deci prima data cand fac Dijkstra, imi ajustez costurile in functie de vectorul de distante reutnat de Bellman-Ford, ceea ce e ok; dar apoi la fiecare pas, faci un Dijkstra, trimiti fluxul prin drumul de augmentare gasit si apoi la urmatorul Dijkstra ajustez costurile in functie de ce a returnat Dijkstra-ul precedent... problema mea e ca intre Dijkstra-ul curent si cel precedent, graful rezidual nu mai e acelasi.. pentru ca am trimis niste flux prin acel graf. Asta inseamna ca eu imi ajustez costurile pe graful rezidual curent in functie de costurile de pe graful rezidual precedent; asta nu ar trebui sa fie o problema?

After all, tot motivul pt care imi ajustez costurile dupa fiecare Dijkstra e ca sa le am actualizate dupa distantele minime din graful rezidual curent, nu?

[•sicsic]

http://www.infoarena.ro/job_detail/1576567
Incerc varianta Bellman-Ford cu coada, dar iau TLE pe testele 6-7. Vreo sugestie?