032 Flux maxim

[•pauldb]

Aici puteti discuta despre problema Flux maxim din Arhiva educationala.

[•gh09]

cum se face fluxul pt graf neorientat ?

ma refer la faptul ca daca ai intre 2 noduri 2 muchii separate (tuneluri) de la a -> b si de la  b -> a pe care poti adauga curent.
la flux clasic adaugi in sensul in care mergi fmin, pe cand  in sensul invers scazi.....deci nu ar fi corect la grafuri neorientate.....


LE: defapt nu cred ca conteaza nu? pt ca la sursa si destinatie nu ai decat numar iesiri, respectiv intrari

[•pauldb]

Singura diferenta este ca daca ai muchie x, y atunci capacitate[ x ][y] = capacitate[y][ x ].

[•andrei-alpha]

Aici pot fi mai multe muchii intre doua noduri ?

[•pauldb]

Da.

[•andrei-alpha]

Atunci nu e prezent in teste ca am laut 100 netratand acest caz.

[•Pepelea_Flaviu]

se trateaza foarte simplu: daca ai intre 2 noduri a si b mai multe muchii cu diferite capacitati, atunci poti considera ca e una singura = cu suma capacitatilor tuturor muchiilor dintre cele 2 noduri

[•andrei-alpha]

Da, ar trebui inclus in teste si cazul cand sunt mai multe muchii ...

[•pauldb]

Am modificat enuntul.

[•Mishu91]

As avea o intrebare... Daca am gasit ca pe muchia [ x,y ] se poate trimite flux, atunci de ce dupa ce s-a adaugat acel flux in F[ x ] [ y ], se si scade din F[ y ][ x ] ?

[•sima_cotizo]

Da, din cate tin minte.

[•Mishu91]

Da, dar de ce?

P.S. Cred ca am formulat cam greoi intrebarea

[•pauldb]

Pentru ca pe muchia y->x fluxul circula in sens contrar. Asta e tocmai magia fluxului si nu permite blocarea retelei pana nu s-a trimis flux maxim.

[•wefgef]

As avea o intrebare... Daca am gasit ca pe muchia [ x,y ] se poate trimite flux, atunci de ce dupa ce s-a adaugat acel flux in F[ x ] [ y ], se si scade din F[ y ][ x ] ?

Depinde de felul in care implementezi. In implementarea mea nu scad fluxul pe muchia inversa, ci imi tin o alta matrice pentru reteaua reziduala.

[•devilkind]

as far as I know, teoria zice ca pe graful rezidual daca pe o muchia x->y avem flux F, atunci pe muchia inversa avem flux -F.  Wef, deci oricum ar fi, atunci cand bagi flux pe muchia x->y, tre sa scoti pe muchie y->x, indiferent de implementare.

De ce e asa? ? it's magic. Vezi pe google poate gasesti niste paper-uri in cu demonstratia algorimtului lui Ford-Fulkerson (sau Edmonds-Karp).

[•Cosmin]

Cliff Stein (http://www.google.com/search?hl=en&q=clifford+stein&btnG=Google+Search&aq=f&oq=) ne zicea recent mie si lui Mircea ca implementarea cu F in o directie si -F pe directia opusa e cam demodata si acuma celor ce lucreaza cu probleme de flux le place cealalta varianta.

Si nu e nici o magie in algoritmi , cand ti se pare ceva magie inseamna ca nu ai inteles problema in totalitate.

[•Mishu91]

Eu unul tot nu m-am lamurit, imi puteti da va rog un exemplu mai mic, usor de urmarit pentru care rezultatul sa dea diferit daca nu scad pe muchia inversa? Pentru ca pe testele oficiale incepe sa pice de la testu' 5 care are 100 de noduri si 200 de muchii, si e cam greu sa-l fac de mana.

[•alexthero]

Incearca-l pe asta:

Cod:

6 7
1 2 1
1 3 1
2 4 1
2 5 1
3 4 1
5 6 1
4 6 1

Tie iti da fluxul 1 (am testat), iar fluxul corect e 2.

[•Mishu91]

Mersi, am inteles

[•gabor_oliviu1991]

am facut algoritmul lui ford fulkerson si iau incorect pe ultimele 4 teste. ( http://infoarena.ro/job_detail/269420 ). din cate am citit in indicatiile de rezolvare, se zica ca algoritmul scoate 100 daca i se face o modificare (pe care sincer n-am inteles-o), dar din cate imi dau seama optimizeaza timpul. probleme cu timpul cred ca n-am, deci de unde ar putea fi problema?

[•Prostu]

am facut algoritmul lui ford fulkerson si iau incorect pe ultimele 4 teste. ( http://infoarena.ro/job_detail/269420 ). din cate am citit in indicatiile de rezolvare, se zica ca algoritmul scoate 100 daca i se face o modificare (pe care sincer n-am inteles-o), dar din cate imi dau seama optimizeaza timpul. probleme cu timpul cred ca n-am, deci de unde ar putea fi problema?

Am trimis sursa ta modificand memseturile din BF si am luat 70 cu TLE pe ultimele 3 teste. Vezi ca am pus un post in topicul de la Ciurul lui Eratostene despre cum se foloseste memsetul. Eu am pus memset(X, 0, sizeof(X)) in loc de memset(X, 0, N).

[•gabor_oliviu1991]

Am cautat pe net detalii despre construirea arborelui BFS, dar nu am gasit mare lucru. Poate sa imi explice cineva cum se face?

[•free2infiltrate]

Am tot incercat sa rezolv problema, si nu inteleg dece imi pica pe testele 4,6,9  . Folosesc metoda descrisa la finalul problemei:
1 construiesc arborele BFS al muchilor nesaturate
2 caut toate drumurile nesaturate de la sursa la destinatie
3 reiau 1 si 2 pana cand toate drumurile sunt saturate

Sursa:
http://infoarena.ro/job_detail/286069?action=view-source

Multumesc de pe acum

[•Robytzza]

Incearca sa-ti aliniezi sursa,ca nimeni nu are curajul sa se uite peste ea asa cum e acuma 

[•mlazari]

Intre oricare doua noduri x si y exista maxim un arc.

Aceasta inseamna ca exista un singur arc de la x la y? Adica poate sa existe maxim un arc de la x la y si unul de la y la x sau doar unul din ele?
Eu daca scriu in program:

Cod:

c[x][y]=z; c[y][x]=0;

obtin 30 puncte, iar daca scriu:

Cod:

c[x][y]=z; //c[y][x]=0;

obtin 100 puncte.
Si inca ceva, compilatorul GNU C++ initializeaza automat variabilele cu 0, sau e preferabil sa le initializez?