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

Timp maxim de executie: 0.1 secunde / test

Prof. Dana Lica
Colegiul Naţional "I.L. Caragiale" Ploieşti
Contact: danal182001@yahoo.com