Adaugarea unei muchii īntr-un arbore
genereaza un ciclu. Presupunem ca introducem o
muchie īntre nodul i si nodul j.
Pentru ca
APM-ul grafului astfel obtinut sa nu se schimbe,
trebuie ca muchia de cost maxim de pe drumul de la
i la j din arborele initial sa aiba costul mai mic
sau egal cu muchia introdusa. Pe aceasta
observatie se bazeaza īntreaga strategie. Se
determina muchiile de cost maxim de pe fiecare
drum dintre oricare doua puncte ale arborelui
initial; se ordoneaza crescator atāt vectorul
acestora cāt si costurile muchiilor care ne sunt
puse la dispozitie. Fisierul de iesire va contine
toate perechile de doua noduri distincte pentru
care avem la dispozitie o valoare mai mare sau
egala cu muchia de cost maxim de pe drumul dintre
cele doua noduri.
Testele sunt
numerotate de la 0 la 9 si se acorda 10 puncte /
test.
|