apm
Se considera un arbore avānd costuri atasate pe muchii si un sir de numere naturale. Sa se adauge arborelui un numar maxim de muchii avānd costuri dintre numerele date, astfel īncāt graful obtinut sa aiba ca arbore partial de cost minim arborele initial.
Date de intrare
Pe prima linie a fisierului text apm.in se afla numarul natural n reprezentānd numarul nodurilor din arbore. Pe urmatoarele n-1 linii se gasesc cāte trei numere naturale separate prin cate un spatiu, sub forma i j c, avānd semnificatia: exista muchie de la i la j avand costul c. Pe urmatoarele linii se afla sirul de numere dat, cāte un numar pe o linie.
Date de iesire
Pe fiecare linie a fisierului de iesire apm.out se vor scrie cate trei numere i j c, avānd semnificatia: "adaugam o muchie īntre nodurile i si j avand costul c". Cele trei numere se vor separa prin cāte un spatiu.
Restrictii si precizari
0<n<256
Costurile muchiilor arborelui sunt
numere naturale nenule <=32000
In sirul de numere dat exista cel
mult 32000 de valori (numere naturale nenule <=30000).
Fiecare element din sir
poate reprezenta costul unei singure muchii adaugate.
Elementele sirului nu
sunt neaparat distincte.
Īntre oricare doua noduri din graf va exista cel mult o
muchie.
Īn cazul īn care nu se poate adauga nici o muchie, īn fisierul de iesire
se va scrie o singura linie ce va contine valoarea 0.
Īn graful obtinut dupa adaugarea
muchiilor pot exista mai multi arbori partiali de cost minim, dar costul
acestora trebuie sa fie identic cu al arborelui initial.
Īn cazul īn care
problema admite mai multe solutii, īn fisierul de iesire se va scrie una
singura.
Exemplu
apm.in | apm.out |
4 1 2 2 3 4 4 3 1 2 2 5 3 |
1
4 5 2 3 3 |
Timp maxim de executie: 0.1 secunde / test
Prof. Dana Lica
Colegiul Naţional
"I.L. Caragiale" Ploieşti
Contact: danal182001@yahoo.com