Pagina principala | Inscriere | Autentificare | Probleme | Clasament pe runde | Clasament | Anunturi | Echipa | Regulament | Linkuri


Vizualizare solutie

Titlul problemei: apm
Numarul problemei: 1
Runda: Runda 1 - Pregatire
Solutie: 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.

Inapoi

© 2002 - 2004 Vālsan Mihai Liviu
Puteti trimite intrebari, comentarii, sau sugestii la adresa liviuvalsan@yahoo.com