229 APDM

[ditzone]

Aici puteţi discuta despre problema APDM.

[•rmikeweb]

Poate cineva sa dea un hint la problema asta.

[•wefgef]

cauta pe algoritmus. are si solutie oficiala.

[•Marius]

Vrei sa imi spui adresa, te rog ? 

[•wefgef]

http://algoritmus.org/index.php

[•sima_cotizo]

Algoritmus nu mai exista sau cel putin linkul nu mai merge...

• Am incercat sa fac dupa postul lui Cho de aici : http://online-judge.uva.es/board/viewtopic.php?p=36766&highlight=%2336766
  Asta ca sa determin nodul din "mijloc" al celui mai lung drum. Gaseam astfel drumul minim si afisam (max+1)/2... Asa iau 20p.
• Apoi am incercat sa fac BFS din nodul ala de mijloc ca sa vad distantele max pana la varfuri, sa sortez distantele si sa le adun pe cele mai mari 2 distante... iar iau 20p, pe alte teste de data asta
• Am incercat si sa adun cele mai mari 2 distante diferite si de data asta iau iarasi 20p...

Stiu ca toate cele 3 metode nu sunt in totalitate corecte, dar as vrea sa stiu si eu daca ideea de baza, comuna, e gresita? ... si eventual care e continuarea 

[•domino]

http://citeseer.ist.psu.edu/cache/papers/cs/701/http:zSzzSzwww.math.tau.ac.ilzSz~hassinzSztree.pdf/hassin97minimum.pdf

[•lamez0r]

la aceasta problema procedez cam asa. parcurg in latime graful pentru fiecare nod si aleg la final cele mai indepartate 2 noduri fata de nodul din care am inceput sa fac parcurgerea. apoi adun aceste distante si astfel aflu diametrul. Primesc 30 de puncte si incorect pe restul testelor. e gresita ideea de rezolvare sau am eroare pe undeva prin program? va multumesc.

[•gabitzish1]

Bogdan, am impresia ca nu ai inteles problema.
Tie nu'ti trebuie distanta dintre cele mai departate doua noduri din graf (si daca ti'ar trebui, nu asta e rezolvarea), ci iti trebuie un arbore partial (un arbore care contine toate nodurile grafului) pentru care distanta intre cele mai departate 2 noduri sa fie cat mai mica.

L.E. : Pe exemplul din problema, daca faci parcurgere in latime din nodul 1, o sa ai d(1,8) = 3 si d(1,3) = 2, deci ar trebui sa'ti dea 5.. raspunsul e 4.

[•ioalexno1]

Are ceva special testul 16?

[•ion824]

Un hint cine a trecut de testul 16...?

[•japjappedulap]

Ce e asa special la testele 9, 10 si 11? Iau incorect pe ele, si nu stiu de ce...