Subarbore

[•wefgef]

Aici se pot pune întrebări legate de problema Subarbore de la Runda 2 a concursului Algoritmiada 2012.

Timpul alocat întrebărilor este de 1 ora. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

[•Protoman]

Subarborele cautat trebuie sa fie conex? Cam asa cred ca e doar ca in enunt nu se precizeaza.

L. E. Mi scuzi

Editat de moderator: LOL

[•CezarMocan]

Fara comentarii.

[•blustudio]

1. APM-ul trebuie sa fie doar pentru cele T noduri speciale sau pentru tot graful?
2. Daca raspunsul la intrebarea precedenta este doar pentru cele T noduri speciale, atunci poate acesta sa contina si alte noduri?

Multumesc!

[•CezarMocan]

1. Problema cere un subarbore de cost minim care sa contina cele T noduri. Nu conteaza ce alte noduri ai sau nu ai, atata timp cat cele T sunt acolo si costul e minim.
2. DA, poate sa contina si altele

[•CezarMocan]

Timpul alocat întrebărilor s-a scurs. Multă baftă în continuare!

[•laurion]

Stiu ca s-a scurs timpul, dar eu nu vad cum da in exemplu 15... nu e corect 16? (costurile sunt 10, 1, 2, 6, 6 -- din numerele astea nu poti scoate 15)

[•dushmi]

6 + 6 + 1 + 2 = 15. Subarborele cerut este cel care contine muchiile 2-1, 1-3, 3-4 si 4-5.

[•laurion]

6 + 6 + 1 + 2 = 15. Subarborele cerut este cel care contine muchiile 2-1, 1-3, 3-4 si 4-5.

ups, merci

[•blustudio]

Ar putea sa-mi spuna cineva ce era gresit in a afla toate perechile de drumuri minime intre nodurile speciale si a face APM-ul pe aceste drumuri, avand in vedere ca nu ne intereseaza care este efectiv drumul cred ca se putea face chiar si cu Roy-Floyd?

[•maritim]

Luai anumite muchii de mai multe ori. De exemplu daca plecai de la un nod special si gasesti o "bifurcatie" si in ambii subarbori se aflau noduri speciale, drumul de la primul nod pana la bifurcatie e luat de 2 ori.

[•david_rauca]

Unde ne mai putem evalua problema ? chiar daca e gata Runda.

[•laurion]

Problemele o sa apara in arhiva