032 Flux maxim

[•darkseeker]

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

[•test9]

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

[•ctlin04]

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  

[•SebiSebi]

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

[•wefgef]

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

[•S7012MY]

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

[•AlexandruValeanu]

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

[•freak93]

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

[•CosminRusu]

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

Sursa : Quora.com

[•manutruta]

Salutare !

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

Multumesc anticipat.

[•SebiSebi]

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.

[•manutruta]

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

[•SebiSebi]

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

[•CosminRusu]

Salutare !

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

Multumesc anticipat.

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.

[•Owlree]

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


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

[•Impaler_009]

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.

[•Owlree]

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

[•SebiSebi]

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.

[•Owlree]

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.

[•SebiSebi]

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.

[•andreiulian]

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

[•PlayLikeNeverB4]

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.

[•andreiulian]

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.

[•varga13]

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.

[•cata00]

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