|
•gh09
Strain
Karma: -2
Deconectat
Mesaje: 38
|
|
« Răspunde #1 : Ianuarie 09, 2009, 20:33:01 » |
|
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
|
|
« Ultima modificare: Ianuarie 09, 2009, 20:39:41 de către chisinau gheorghita »
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #2 : Ianuarie 09, 2009, 21:07:10 » |
|
Singura diferenta este ca daca ai muchie x, y atunci capacitate[ x ][y] = capacitate[y][ x ].
|
|
« Ultima modificare: Ianuarie 09, 2009, 21:12:25 de către Sima Cotizo »
|
Memorat
|
Am zis
|
|
|
•andrei-alpha
Client obisnuit
Karma: 103
Deconectat
Mesaje: 91
|
|
« Răspunde #3 : Ianuarie 12, 2009, 14:38:42 » |
|
Aici pot fi mai multe muchii intre doua noduri ?
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #4 : Ianuarie 12, 2009, 16:56:09 » |
|
Da.
|
|
|
Memorat
|
Am zis
|
|
|
•andrei-alpha
Client obisnuit
Karma: 103
Deconectat
Mesaje: 91
|
|
« Răspunde #5 : Ianuarie 12, 2009, 23:20:05 » |
|
Atunci nu e prezent in teste ca am laut 100 netratand acest caz.
|
|
|
Memorat
|
|
|
|
•Pepelea_Flaviu
Client obisnuit
Karma: 30
Deconectat
Mesaje: 98
|
|
« Răspunde #6 : Ianuarie 13, 2009, 12:30:22 » |
|
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
|
|
« Ultima modificare: Ianuarie 13, 2009, 18:48:52 de către Flaviu Pepelea »
|
Memorat
|
|
|
|
•andrei-alpha
Client obisnuit
Karma: 103
Deconectat
Mesaje: 91
|
|
« Răspunde #7 : Ianuarie 13, 2009, 21:15:42 » |
|
Da, ar trebui inclus in teste si cazul cand sunt mai multe muchii ...
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #8 : Ianuarie 13, 2009, 22:48:19 » |
|
Am modificat enuntul.
|
|
|
Memorat
|
Am zis
|
|
|
•Mishu91
|
|
« Răspunde #9 : Ianuarie 19, 2009, 17:44:43 » |
|
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 ] ?
|
|
|
Memorat
|
|
|
|
•sima_cotizo
|
|
« Răspunde #10 : Ianuarie 19, 2009, 18:04:54 » |
|
Da, din cate tin minte.
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #11 : Ianuarie 19, 2009, 18:14:40 » |
|
Da, dar de ce?
P.S. Cred ca am formulat cam greoi intrebarea
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #12 : Ianuarie 19, 2009, 20:51:04 » |
|
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.
|
|
|
Memorat
|
Am zis
|
|
|
•wefgef
|
|
« Răspunde #13 : Ianuarie 19, 2009, 20:53:09 » |
|
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.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•devilkind
|
|
« Răspunde #14 : Ianuarie 19, 2009, 22:49:51 » |
|
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).
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #15 : Ianuarie 19, 2009, 23:18:17 » |
|
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.
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #16 : Ianuarie 20, 2009, 21:44:41 » |
|
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.
|
|
« Ultima modificare: Ianuarie 20, 2009, 22:02:34 de către Andrei Misarca »
|
Memorat
|
|
|
|
•alexthero
|
|
« Răspunde #17 : Ianuarie 20, 2009, 22:08:16 » |
|
Incearca-l pe asta: 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.
|
|
|
Memorat
|
Tine minte ca mintea conduce pumnu, nu invers
|
|
|
•Mishu91
|
|
« Răspunde #18 : Ianuarie 20, 2009, 22:21:43 » |
|
Mersi, am inteles
|
|
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #19 : Martie 02, 2009, 21:40:03 » |
|
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?
|
|
|
Memorat
|
|
|
|
•Prostu
|
|
« Răspunde #20 : Martie 07, 2009, 13:10:15 » |
|
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).
|
|
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #21 : Martie 13, 2009, 00:31:01 » |
|
Am cautat pe net detalii despre construirea arborelui BFS, dar nu am gasit mare lucru. Poate sa imi explice cineva cum se face?
|
|
|
Memorat
|
|
|
|
•free2infiltrate
Strain
Karma: -25
Deconectat
Mesaje: 41
|
|
« Răspunde #22 : Martie 23, 2009, 16:14:16 » |
|
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-sourceMultumesc de pe acum
|
|
|
Memorat
|
|
|
|
•Robytzza
|
|
« Răspunde #23 : Martie 24, 2009, 14:54:08 » |
|
Incearca sa-ti aliniezi sursa,ca nimeni nu are curajul sa se uite peste ea asa cum e acuma
|
|
|
Memorat
|
|
|
|
•mlazari
Strain
Karma: 8
Deconectat
Mesaje: 28
|
|
« Răspunde #24 : Mai 20, 2009, 17:42:50 » |
|
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: obtin 30 puncte, iar daca scriu: obtin 100 puncte. Si inca ceva, compilatorul GNU C++ initializeaza automat variabilele cu 0, sau e preferabil sa le initializez?
|
|
|
Memorat
|
|
|
|
|