Pagini recente » Diferente pentru problema/maxsecv intre reviziile 8 si 9 | Diferente pentru problema/superp intre reviziile 8 si 3 | Monitorul de evaluare | Diferente pentru problema/split2 intre reviziile 11 si 10 | Diferente pentru problema/cactus intre reviziile 1 si 2
Diferente intre titluri:
Diferente intre continut:
== include(page="template/taskheader" task_id="cactus") ==
Poveste şi cerinţă...
_-Matei Nakayama- Mihai a primit un cactus._
Un cactus este un graf conex neorientat în care fiecare nod face parte din cel mult un ciclu. Se consideră un cactus cu N noduri şi M muchii cu diverse lungimi. Acesta nu conţine bucle (adică muchii între un nod şi el insuşi) sau muchii paralele (adică două sau mai multe muchii între o singură pereche de noduri).
Mihai vrea să elimine muchii din graful cactus, astfel încât să obţină un arbore cât mai uşor. Distanţa dintre două noduri din arbore este egală cu suma lungimilor muchiilor de pe cel mai scurt drum dintre cele două noduri. Greutatea unui arbore este definită ca fiind suma distanţelor dintre oricare două perechi neordonate de noduri distincte - perechea (1, 2) este echivalentă cu perechea (2, 1).
Ajutaţi-l pe Mihai să găsească *greutatea minimă* a unui arbore obţinut prin eliminarea unor muchii din cactus.
h2. Date de intrare
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
