1226 Retea2

[•wefgef]

Aici puteţi discuta despre problema Retea2.

[•maritim]

E suficient algoritmul lui Kruskal pentru a face problema aceasta (si cum) sau e nevoie de algoritmul lui Prim?

[•dushmi]

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

[•maritim]

Mersi frumos. Partea cu memoria ma deranja pe mine cel mai mult, acum ca m-am lamurit o sa incerc implementarea algoritmului lui Prim.

[•scipianus]

Are ceva special testul 15? 

[•mathboy]

Incearca sa afisezi cu 7 zecimale rezultatul.

[•scipianus]

A mers asa Mersi 

[•tzipleatud]

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 . Multumesc anticipat!