|
Titlul: 1226 Retea2 Scris de: Andrei Grigorean din Decembrie 11, 2011, 15:02:55 Aici puteţi discuta despre problema Retea2 (http://infoarena.ro/problema/retea2).
Titlul: Răspuns: 1226 Retea2 Scris de: Cristian Lambru din Decembrie 11, 2011, 16:18:13 E suficient algoritmul lui Kruskal pentru a face problema aceasta (si cum) sau e nevoie de algoritmul lui Prim?
Titlul: Răspuns: 1226 Retea2 Scris de: Mihai-Alexandru Dusmanu din Decembrie 11, 2011, 16:28:05 Kruskal necesita o sortare a muchiilor. Aici nu prea ai destula memorie pentru a retine toate muchiile ceea ce face imposibila folosirea acestui algoritm.
In al doilea rand, graful de aici este complet si, dupa cum este precizat si in explicatiile de la APM, este recomandata folosirea algoritmului Prim in O(N ^ 2). O explicatie destul de buna se poate gasi aici (http://en.wikipedia.org/wiki/Prim%27s_algorithm#Description). Pentru a-ti face treaba mai usoara poti considera toate centralele ca fiind un singur nod care are d[ i ] = distanta pana la blocul i = minimul distantelor de la centrale la blocul i. Acum problema ramane doar gasirea APM-ului in graful format din cele m blocuri + supernod-ul corespunzator centralelor. Titlul: Răspuns: 1226 Retea2 Scris de: Cristian Lambru din Decembrie 11, 2011, 16:38:12 Mersi frumos. Partea cu memoria ma deranja pe mine cel mai mult, acum ca m-am lamurit o sa incerc implementarea algoritmului lui Prim.
Titlul: Răspuns: 1226 Retea2 Scris de: FMI Ciprian Olariu din Decembrie 11, 2011, 17:24:01 Are ceva special testul 15? ???
Titlul: Răspuns: 1226 Retea2 Scris de: Dragos-Alin Rotaru din Decembrie 11, 2011, 17:25:27 Incearca sa afisezi cu 7 zecimale rezultatul.
Titlul: Răspuns: 1226 Retea2 Scris de: FMI Ciprian Olariu din Decembrie 11, 2011, 17:39:22 A mers asa :ok: Mersi :D
Titlul: Răspuns: 1226 Retea2 Scris de: Tudor Tiplea din Ianuarie 13, 2012, 18:35:32 Salut! Am incercat problema asta si cu algoritmul lui Kruskal si pe cel al lui Prim insa iau doar un test corect in ambele cazuri si nu imi dau seama de ce? Daca ar putea cineva sa posteze vreun test mai mare sau cu ceva caz special sa imi dau si eu seama care o fi problema as fi recunoscator :D . Multumesc anticipat!
|