032 Flux maxim

[•wefgef]

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?

[•mlazari]

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 si am urmat pasii, dar nu compila, imi aparea un mesaj de eroare (nu-mi mai amintesc care).

[•Mishu91]

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?

[•gabitzish1]

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

[•wefgef]

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

[•Goten]

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

[•toni2007]

Cu ce compilezi ?

[•Goten]

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

[•Mishu91]

Am testat sursa asta 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?

[•Goten]

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.

[•alexandru92]

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 ?

[•sima_cotizo]

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

[•alexandru92]

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 ?

[•sima_cotizo]

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.

[•APOCALYPTO]

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

[•dornescuvlad]

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

[•APOCALYPTO]

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

[•PlayLikeNeverB4]

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.

[•promix2012]

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

[•dornescuvlad]

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.

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

[•PlayLikeNeverB4]

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.

[•dornescuvlad]

Scuze, atunci! 

[•raduberinde]

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

[•rusu_radu]

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

[•test9]

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!