infoarena

Aici puteti discuta despre problema Flux maxim (http://infoarena.ro/problema/maxflow) din Arhiva educationala (http://infoarena.ro/arhiva-educationala).

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

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

Aici pot fi mai multe muchii intre doua noduri ?

Da.

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

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

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

Am modificat enuntul.

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 ] ? :D

Da, din cate tin minte.

Da, dar de ce?

P.S. Cred ca am formulat cam greoi intrebarea

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.

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

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).

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.

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.

Incearca-l pe asta:

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

Mersi, am inteles :D

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).

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

Am tot incercat sa rezolv problema, si nu inteleg dece imi pica pe testele 4,6,9  :sad: . 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

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

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?

Toate variabilele globale sunt initializate cu 0, pe cand cele locale nu sunt initializate - pot avea orice valoare.

Se pare ca pot exista muchii x->y si y->x.

P.S.: Tocmai am citit regulamentul olimpiadei din Moldova. Voi aveti la dispozitie doar Pascal? :shock:

In fiecare an era pus la dispozitie atat Pascal, cat si C/C++ si erau 2 zile de concurs. Anul acesta intr-adevar in regulament era scris ca e permis doar Pascal, dar pe desktop se gaseau 3 pictograme alaturate: Turbo Pascal, Free Pascal si DevCpp, iar olimpiada a fost intr-o singura zi: 4 probleme in 4 ore, la fel ca si barajul. M-am uitat in sursele celorlalti si am vazut la cineva si surse in C++  ??? Probabil nu fusese atent la regulament... Oricum eu am preferat Free Pascal decat DevCpp, pentru ca l-am instalat acasa si e aproape imposibil sa fac debug cu el. Acum mi-am instalat CodeBlocks si sunt multumit, in afara de faptul ca trebuie sa creezi un proiect ca sa poti faci debug  :) RHIDE n-am mai inteles cum se instaleaza... Am gasit pe infoarena un articol despre instalare: http://infoarena.ro/djgpp-instalarea-de-la-a-la-z (http://infoarena.ro/djgpp-instalarea-de-la-a-la-z) si am urmat pasii, dar nu compila, imi aparea un mesaj de eroare (nu-mi mai amintesc care).

Am o întrebare legată de flux. Cum trebuie să modific algoritmul dacă, pe lângă capacitățile maxime ale muchiilor se dau și capacitățile minime?

S-a dat anul trecut la .campion la grupa Large o problema de genul asta, http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=78 (http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=78). Nu stiu unde poti gasi acum solutia, dar stiu ca se facea trimitere in Cormen, pe la sfarsitul capitolului de flux... acolo scrie ceva despre flux cu capacitati inferioare si superioare.

Eu am luat 100 pe problema respectiva dar nu am facut "ca la carte"... am bagat un flux de mai multe ori modificand ceva capacitati pe acolo... nu mai stiu exact ce'am facut in sursa aia  :shock: .

E destul de complicat algoritmul. Ti-as recomanda sa citesti din Cormen la capitolul de flux.

Am luat testele 1,5 si 10 + exemplu' si merg la mine pe calculator. Aici iau zero. De ce oare?

Cu ce compilezi ?

MinGW, da' de cand am intrat pe infoarena lucrez pe asta si n-am avut probleme.

Am testat sursa asta (http://infoarena.ro/job_detail/389635?action=view-source) la mine pe calculator (pe același compilator ca și cel de pe infoarena) și pe exemplu dă 7 în loc de 8. Ești sigur că îți dă bine ție?

O luai si-o testai in Borland si observai ca problema era ca la citire.
Eu citeam f>>x>>y>>c[ x][y] si aici apareau problemele. In MinGW mergea bine, da' in Borland nu-mi lua toate valorile o.0.
Multumesc de ajutor.

Daca as avea mai multe susre si mai multe destinatie. Cum fac sa determin pentru fiecare sursa->destinatie fluxul maxim. Adaug o super_sursa si o super_destinatie si apoi determin drumul de flux maxim sau exista alta metoda ?

Super sursa/destinatie suna bine. Si cred ca e cel mai usor.

Da, dar daca am X intrebari de genu : care este fluxul maxim pentru sursa_i -> destinatia_i ? Dupa ce am determinat fluxul maxim folosind ideea de mai sus determin drumul de lungime maxima dintre sursa_i si destinatia_i ?

Citisem aiurea, credeam ca intrebi de problema clasica cu mai multe surse/destinatii :) In cazu asta, cred ca merge ideea cu o super-destinatie + faci flux pentru fiecare sursa separat (bineinteles, izoland de fiecare data celelalte surse)... bineinteles, e posibil sa fie si alta idee mai eficienta.

Este ceva ciudat cu testele 5-7?
Abia am reusit sa trec testul 5 dupa ce mi-am ciopartit sursa ca sa semene cu a lui Tiberiu (in care folosesc algoritmul de 70 de puncte):
- am scris coada de mana in loc de queue din STL
- am inlocuit int cu short pe unde se putea
- am incercat sa vad daca e mai rapida sursa cu streamuri sau cea cu citire standard
- am declarat vectorul viz[] ca bitset si ca short
- am parsat citirea
- am incercat sa parcurg listele de adiacenta atat cu iteratori din STL cat si cu iteratori normali

Salut, nu e nimic ciudat la testele 5-7.
Uite sursa ta, modificata, de 90 de puncte (daca nu luam in calcul testele grupate).
http://infoarena.ro/job_detail/475716?action=view-source
Nu mai tin minte exact toate modificarile pe care le-am facut.Tin minte ca am inlocuit <bitset> cu un vector int pe care il setez mereu la 0 cand revin in functia BFS() pentru a-mi construi un nou drum (tu parca declarai bitsetul in functia BFS(), daca tin bine minte).
Alta modificare pe care am facut-o a fost la declararea cozii.Tu aveai declarata o coada de aproximativ 250 elemente, desi numarul maxim de noduri e 1000.
Am redus si numarul de subprograme (cit(), solve())..nu stiu daca a contat in vreun fel...

10x.
Dar adevarata modificare era fmin = 2891821; :aha: am pus asta la prima sursa de 50 si am luat 80(cu testul 8 grupat).

Aveti idee de ce imi da Incorect la 5,6,7,9?
Folosesc ideea de pe topcoder.
Sursa mea: http://infoarena.ro/job_detail/498661?action=view-source

Edit: Dupa 3 luni :-', am gasit greseala: C[y][ x]=0. Am omis si eu faptul ca pot exista arcele x->y si y->x in acelasi timp. Totusi din enunt ("Intre oricare doua noduri x si y exista maxim un arc.") nu prea reiese asta. Sau daca reiese, e mult prea subtil.

ma poate ajuta cineva si pe mine cu sursa http://infoarena.ro/job_detail/581257 ....nu inteleg ce e gresit.... ](*,)

Pai arcele inverse nici nu exista. :))
Alea le pui tu (sunt inaginare, de aia au capacitatea 0) ca sa te poti intoarce pe ele si sa gasesti alte drumuri de ameliorare. (ca fluxul sa fie maxim).

Postul e vechi rau :) Sunt destul de sigur ca exista teste in care sunt muchii de genul ala (si nu cele "imaginare"). Citeste mai atent sa intelegi la ce ma refeream.

Scuze, atunci!  :D

Nu prea inteleg care e treaba cu optimizarea. Se poate sa iti iei teapa si sa te uiti la O(N) drumuri si numai primul drum sa fie folositor. Ceea ce ar lua O(N^2) in loc de O(M) pentru fiecare BF.


Un exemplu limitat ar fi un graf  1->2->3->.. -> N-1 si muchii de la 2->N, 3->N etc. Si sa zicem ca muchia 1->2 are capacitate 1 si restu muchiilor au capacitate mai mare.

Daca faci fara optimizare faci un BF, gasesti un drum si gata, ceea ce e O(N). Daca faci cu optimizarea, o sa incerci toate drumurile (care se termina in 2->N, in 3->N, in 4->N, etc.) si e degeaba ca oricum dupa primul drum nu o sa mai gasesti nimic - si asta ar lua O(N^2).

Stiu ca oricum nu prea conteaza ca e fluxul 1 da sunt sigur ca s-ar gasi exemple similare mai dramatice (in care s-ar gasi alte drumuri dar chiar esti nevoit sa faci un BF nou de fiecare data).

Dpdv teoretic nu cred ca se poate demonstra ca optimizarea reduce numarul de BF-uri in toate cazurile.. Deci complexitatea teoretica creste la O(N^3*M) in loc de O(N*M^2)..

Poate nu inteleg eu ceva..

Hey!

Am incercat si eu problema asta dar nu am folosit metoda cu graful rezidual!

Am facut si optimizarea respectiva dar totusi nu ma prind de ce iau Incorect pe 3 teste ](*,)!

Ma poate cineva ajuta cu un test sau cu o idee!

Asta e sursa
http://infoarena.ro/job_detail/708467?action=view-source

Thx!

LE: Am gasit problema :)), am rezolvat-o, dar acuma am probleme cu timpul :))!

Salut. Am o intrebare:
A luat cineva 100 de puncte cu "Ford-Fulkerson" ? Ca eu de ieri ma tot chinui si iau 70 cu tle pe ultimele 3 teste, unde se pare ca-mi face mai mult de 200.000.000 de lanturi...
Multumesc anticipat!

Pentru 100 de pct este necesara optimizarea prezentata in indicatiile de rezolvare.

Gata, am luat 100 cu Edmonds-Karp, multumesc de ajutor
@cosmin, eu am facut indicatia aia prima oara in felul in care am inteles-o (gresit se pare), am facut un DFs la care nu reluam de fiecare data lantul de la inceput. Chestia e ca m-am bazat pe faptul ca atunci cand modifici un lant se modifica si o muchie (fluxul din ea devine maxim, si n-o sa mai fie nevoie s-o mai iei inca o data), dar uite ca pe unele teste nu e asa ..

Ma ajuta cineva si pe mine sa iau 100 la problema asta, daca am inteles bine acea optimizare atunci cred ca am facut-o, dar tot nu pot lua mai mult de 70  ](*,) http://infoarena.ro/job_detail/775701. Va rog uitativa cineva pe sursa mea si spuneti-mi daca am implimentat corect optimizarea si daca nu va rog explicati-mi printr-un exemplu in ce consta aceasta optimizare pentru 100 de puncte  :sad:

Salut!
Daca determin ponderea taieturii minime cu ajutorul algoritmului de flux, cum pot sa gasesc si cele doua multimi, V1 si V2? Multumesc!

Faci un DFS din sursa pe muchiile nesaturate. Nodurile pe care le vizitezi fac parte din prima multime.

http://www.cs.tufts.edu/comp/260/lect2-11.pdf Demonstratia complexitatii la edmonds karp

Am si eu o nelamurire: optimizarea pentru 100p nu e de fapt algoritmul lui Dinic?

E prost articolul de pe infoarena legat de flux. Algoritmul lui Dinic nu e acela, se bazeaza pe alt principiu.

Se pare ca in 2012 s-a descoperit un nou algoritm de flux maxim, mult mai rapid, cu o complexitate de aproximativ O ( N * M ).

Pentru cei interesati algoritmul este descris aici (http://math.mit.edu/~kelner/Publications/Docs/maxFlow.pdf)

Sursa : Quora.com (http://www.quora.com/Algorithms/Have-there-been-any-new-brilliant-computer-science-algorithms-in-last-10-years)

Salutare !

Am si eu o interbare: Cum ar fi algoritmul de flux pentru un graf neorientat ?

Multumesc anticipat.

Este la fel ca cel într-un graf orientat, doar ca în graful rezidual apare și muchia x->y și y->x de capacitate C.

Deci in graful normal, o sa am 2 muchii: x->y si y->x, de cost c.
Construiesc graful rezidual de data asta (pe grafuri orientate pur si simplu adaugam muchie in graful normal) cu muchii asa: x->y si y->x de cost 0.

Astfel, voi avea 2 matrici de capacitate si 2 matrici de flux ?
Multumesc. Implementarea asta m-i se pare destul de mult complicata fata de grafuri orientate...

Nu trebuie sa folosești doua matrici. Singura modificare este ca muchia "inversa" are și ea tot aceeași capacitate și nu 0.

Salut!
Sebi are dreptate, practic cand iti construiesti graful pui capacitate C si pe muchia y -> x, nu doar pe x -> y.
Ar mai fi o idee destul de inteligenta si anume fiecare nod x il transformi in doua noduri, fie ele x1 si x2, astfel ca in x1 vor intra toate muchiile incidente in x si din x2 vor iesi toate muchile care ies din x (iar intre x1 si x2 ai capacitate infinita). Mai exact pentru o muchie neorientata x-y o sa bagi in graful tau urmatoarele muchii orientate: x2 -> y1 si y2 -> x1. Si astfel am redus problema la flux maxim intr-un graf orientat.

Pentru dumnezeu, da ce m-am chinuit cu problema asta.

Scriu aici că poate o să ajute pe cineva pe viitor.

În problemă pot exista maximum 2 arce între oricare două noduri, în cazul în care sunt exact 2, acestea sunt antiparalele. Spre exemplu putem un arc de la A la B și, în același timp, unul de la B la A. Asta e ce li se pare unora ciudat pe testele 5, 7, și care or mai fi.

Există soluții care aici pe evaluator iau 100 de puncte din noroc chior, acestea fiind greșite. Eu am luat 70 cu o astfel de soluție, trecând inclusiv și testul 5, care, am verificat, are cel puțin două arce antiparalele (72 -> 34 și 34 -> 72, liniile 72 și 156).

Dacă implementezi o metodă Ford-Fulkerson (cum ar fi Edmonds-Karp), ca să nu-ți scoți limba prin urechi de nervi, fă bine și tratează și cazul ăsta. Se tratează ușor. Dacă avem arcele A -> B și B -> A, de capacitate f(A, B) și respectiv f(B, A), pur și simplu adăugăm un nod C și rearanjăm astfel: A -> C, C -> B și B -> A, primelor două de dăm capacitatea f(A, B), iar celei din urmă capacitatea f(B, A). Practic facem același drac, da o luăm pe ocolite puțin.

Mai jos aveți un exemplu mai concret. Există arce antiparalele între nodurile v₁ și v₂, rezolvăm problema prin adăugarea nodului v'.
(http://i61.tinypic.com/24cz6s1.png)

Atenție să declarați limitele cum trebuie deoarece acum pot fi mai mult de 1000 de noduri.

De ce nu vrem să avem arce antiparalele? Este explicat foarte bine în Introduction to Algorithms, 3rd Edition (CLRS) (http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844) - 26.1 Flow Networks. Tot acolo găsiți și demonstrații și alte explicații. Țin să menționez că tot din aceeași cartea am luat și imaginea de mai sus, pagina 711.

Nu este nevoie sa tratezi muchiile antiparalele daca implementezi cu grija algoritmul.  In Cormen ti se spune sa faci asa pentru ca ei acolo stabilesc o conventie cand definesc o retea de flux (ca intre x si y poti avea o muchie cu un singur sens si deci in graful rezidual fiecare muchie are o pereche cu capacitate 0). Dar poti s-o tratezi si altfel: daca exista si x->y si y->x, amandoua apar in graful rezidual cu capacitatea lor. Restul rezolva algoritmul de la sine. Plus ca daca rezolvi probleme de flux pe un graf neorientat e cam ineficient sa adaugi M noduri.

Dar sunt de acord ca ori enuntul ori testele trebuie modificate.

Da, ai dreptate, dar aici problema e că la tine cu grijă înseamnă să știi că există și arcele astea.

Și eu l-am implementat cu grijă (eh, atât cât se poate), dar am presupus faptul că nu există.

Nu trebuie implementat cu grija, nici nu trebuie sa te gândești dacă exista sau nu muchii antiparalele. Pur si simplu fiecare muchie are capacitatea ei. Bagi Edmonds-Karp si sigur vei obține rezultatul corect.

Dacă implementezi cu liste de adiecență probabil nu e nevoie, dar dacă implementezi cu matrice o să ai ceva probleme pentru că presupunem că în graful rezidual u -> v e cât mai putem să trecem prin arcul de la u la v și v -> u cât am trecut deja, apoi dacă ar exista în rețea și arcul v -> u simultan, arcele în graful rezidual ar avea un înțeles ambiguu. Poți desigur să menții două matrice de graf rezidual, dar deja dezvoltăm prea mult un subiect care nu e chiar atât de important.

Oricum, enunțul a fost modificat, zic acum să sărbătorim. :yahoo:

Nu e nevoie sa memorezi doua matrice. Gândește-te ce ce întâmpla când ai grafuri neorientate. Daca graful contine arce antiparalale atunci in graful rezidual vei avea capacitați nenule pentru x->y și y->x.

Am o problemă. Începând cu testul 4 primesc "Incorect", dar am descărcat testele și îmi dă bine. Las un link către sursa mea
http://www.infoarena.ro/job_detail/1340185?action=view-source

Nu stiu care e rostul vectorului drum, dar oricum depasesti limitele vectorului (din cauza lui u) si scrii peste tot in memorie si suprascrii multe valori de care ai nevoie.

Mulțumesc mult !  Cred că eram obosit când am scris programul. Acum iau 70 de puncte, dar dacă nu erau grupate ultimele 3 luam 80. Mulțumesc din nou.

salut. am incercat o implementare(mai mult sau mai putin reusita) la edmonds-karp, si pe primul test cel putin rezultatul e corect(conform atasamentelor) si vroiam sa cer o parere. Iau 0 desi cand verific testul rezultatul imi e 683.
merci.

Noroc,

Testele 2-3 și 5-10 conțin muchii multiple între aceeași pereche de noduri. Sub GNU/Linux, le puteți lista cu:

  cut -f 1-2 -d ' ' grader_test2.in|sort|uniq -d

M-am gândit că poate unele surse se poticnesc de asta. :-)

Numai bine,
Cătălin

Din enunt:

Intre oricare doua noduri x si y exista maxim un arc, însă arcele x -> y şi y -> x pot exista simultan.

Insa in testul 5 exista doua arce 60 84 10227 si 60 84 4334 (liniile 84 si 176 din fisierul de intrare)  :)