|
ditzone
Vizitator
|
 |
« : Octombrie 15, 2006, 21:28:53 » |
|
Aici puteţi discuta despre problema Cc. |
|
|
|
|
Memorat
|
|
|
|
|
•peanutz
|
|
« Răspunde #1 : Octombrie 17, 2006, 21:43:34 » |
|
Fac un vector de struct cu 3 variabile: copil, calc si cost.... apoi sortez dupa cost. Si fac un greedy luand pe cele de la inceput si adaugand in costmin daca nu figureaza intr-un vector uz dupa care adaug elementul actual in uz(atat calc cat si copil)... E bun algoritmul sau incomplet?
|
|
|
|
|
Memorat
|
....staind....
|
|
|
|
Chris
Vizitator
|
|
« Răspunde #2 : Octombrie 17, 2006, 22:38:41 » |
|
Nu e nici bun, nici incomplet.  Problema este clasica : se cere un cuplaj bipartit maxim de cost minim. Asta se poate rezolva cu flux maxim de cost minim. Cauta un tutorial pe net. Din cate tin minte in Cormen nu e explicat. (totusi te-as sfatui ca prima data sa te uiti peste algortimii: Ford-Fulkerson si Bellman-Ford si dupa aia sa incerci sa-l implementezi). Spor! |
|
|
|
|
Memorat
|
|
|
|
|
•peanutz
|
|
« Răspunde #3 : Octombrie 17, 2006, 23:12:17 » |
|
Mi-am dat si eu seama ca e bipartit..... si cam atat  ) De vreo 2 zile tot incerc.... tot imi iasa pana la urma  Merci pentru sfat!!! |
|
|
|
|
Memorat
|
....staind....
|
|
|
|
•cos_min
|
|
« Răspunde #4 : Noiembrie 15, 2006, 21:46:09 » |
|
Construiesc un graf cu 2*n+1 noduri. Nodul sursa 0 si nodul destinatie 2*n+1. Capacitatiile in graf sunt 1 peste tot. Cost de la nodul i [1..n] pana la nodul j [n+1..2*n] este in matr citita c[i ][j-n]. Dupa care fac algoritmul de flux maxim de cost minim, si cam atat. Si la afisare adun costul nod de la n+1 ... 2*n.
Ii bine ce fac si probabil gresesc undeva la implementare ? Sau trebuie modificat ceva si in alg de flux maxim de cost minim?
|
|
|
|
« Ultima modificare: Martie 25, 2007, 08:34:16 de către Valentin Stanciu »
|
Memorat
|
vid...
|
|
|
|
•cos_min
|
|
« Răspunde #5 : Noiembrie 18, 2006, 15:06:07 » |
|
deci ma poate ajuta cineva?  |
|
|
|
|
Memorat
|
vid...
|
|
|
|
•vladcyb1
|
|
« Răspunde #6 : Noiembrie 19, 2006, 10:25:22 » |
|
Vezi sa ai grija sa pui cost negativ pe muchiile de intoarcere.
|
|
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
|
•sima_cotizo
|
|
« Răspunde #7 : Ianuarie 04, 2007, 19:17:32 » |
|
Ok, toate bune si frumoase, dar pana la pasul 4. Nu am implementat algoritmul, dar am facut "de mana"... Am ajuns la cazul in care avem copii 2 si 4 liberi si calculatoarele 1 si 5. Copilul 4 face distanta 6 pana la oricare calculator, copilul 2 prefera sa se aseze la comp 1 ca e mai aproape. Dar bellman-ford (sau dijkstra) il poate aseza pe copilul 2 la comp 1 si se strica tot. Eu nu inteleg chestia asta, ca pot exista exemple in care e invers, copilul 2 se aseaza la comp 5 ca e mai aproape...  eu unul nu inteleg cum merge algoritmul asta, decat in mare... si complexitatea ajunge [dupa mine] la N^3, caz in care ar putea fi rezolvata cu un roy-floyd... un pic de help, please!  |
|
|
|
|
Memorat
|
|
|
|
•gurney
Strain
Karma: -6
 Deconectat
Mesaje: 10
|
|
« Răspunde #8 : Martie 24, 2007, 16:13:37 » |
|
-din cate stiu bellman ford se face in O(n^3) de unde cea finala o(n^4).Cum ajung la o(n^3)total?  |
|
|
|
|
Memorat
|
|
|
|
|
•wefgef
|
|
« Răspunde #9 : Martie 24, 2007, 17:42:47 » |
|
Incearca sa faci Bellman-Ford cu coada. In practica merge mult mai bine.
|
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•gurney
Strain
Karma: -6
Deconectat
Mesaje: 10
|
|
« Răspunde #10 : Martie 27, 2007, 19:31:29 » |
|
-Da, se pare ca se comporta mai bine. Mersi, bafta la oni.  |
|
|
|
|
Memorat
|
|
|
|
|
•devilkind
|
|
« Răspunde #11 : Martie 27, 2007, 19:45:13 » |
|
algoritmu ungar intra??? adik eu iau 20 de puncte si mi se pare destul de ciudat.  Am gresit eu la implementare si imi cicleaza undeva sau nu se incadreaza in timp. (iau 8 TLE-uri) |
|
|
|
|
Memorat
|
|
|
|
|
•CezarMocan
|
|
« Răspunde #12 : Martie 27, 2007, 21:13:43 » |
|
Eu cu ungaru am luat 100... |
|
|
|
|
Memorat
|
|
|
|
|
•domino
|
|
« Răspunde #13 : Martie 27, 2007, 21:30:33 » |
|
Eu cu ungaru am luat 100...  Ungar nu e tocmai cel mai usor de implementat algoritm pentru asta. Folositi flux maxim de cost minim, fie cu Bellman Ford cu coada, fie cu Dijkstra. |
|
|
|
« Ultima modificare: Martie 27, 2007, 22:02:34 de către Bogdan Tataroiu »
|
Memorat
|
|
|
|
•vanila0406
De-al casei
Karma: -174
Deconectat
Mesaje: 107
Be wise,be smart,be like me!
|
|
« Răspunde #14 : Martie 28, 2007, 23:39:21 » |
|
Da...si eu am luat 100 cu ungar...dar am gasit intro carte de o explicatie cu dijkstra...desi ungar mi se pare mult mai usor de inteles...chiar daca este foarte costisitor la implementare
|
|
|
|
|
Memorat
|
Only one thing I know:Death is the best way to a better life.
|
|
|
|
•Florian
|
|
« Răspunde #15 : Aprilie 25, 2007, 13:26:50 » |
|
Cu back se poate lua mai mult de 10 puncte???  |
|
|
|
|
Memorat
|
|
|
|
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena