Pagina principala | Inscriere | Autentificare | Probleme | Runde | Clasament | Anunturi | Echipa | Regulament | Exit


Vizualizare solutie pentru problema: trip

Titlul problemei trip
Grupa Grupa B
Problema numarul 2
Runda numarul 11
Solutie oficiala Problema cere sa se gaseasca 2 drumuri intre 2 noduri, drumuri care sa aiba cat mai putin muchii comune. Observatie cheie este ca intr-o componenta biconexa exista un ciclu intre oricare doua noduri (deci exista doua drumuri disjuncte).
Singurele muchii care vor fi parcurse de doua ori sunt muchiile critice care despart componentele biconexe.

Primul pas care trebuie facut este de a gasi componentele biconexe ale grafului. Acest lucru se poate face cu o parcurgere in adancime in O(n+m).
Al doilea pas ar fi gasirea unui drum intre sursa si destinatie care sa treaca prin cat mai putine componente biconexe. Pentru aceasta se asociaza fiecarei muchii (a,b) un cost astfel:
c[a,b]=0 daca a si b sunt in aceeasi componenta biconexa si
c[a,b]=1 daca a si b sunt in componenete biconexe diferite.
Pentru a gasi drumul se poate folosi fie algoritmul lui Dijkstra, fie se poate face o parcurgere in latime putin modificata: daca relaxam o muchie de cost 1 adaugam noul nou la sfarsitul cozii, altfel il adaugam la inceputul cozii. Acest lucru se poate implemeta fie cu liste alocate dinamic, fie cu un vector de dimensiune dubla in care nodul de plecare se pune pe pozitia din mijloc (pentru a avea suficient loc si inaintea lui si dupa el pentru a adauga toate nodurile). Cine are indemanare poate sa incerce sa implementeze o lista circulara.
Atentie: e posibil sa punem un nod de doua ori in lista.
Pasul final consta in a elimina din graf toate componentele biconexe care sunt sunt parcurse de drumul gasit mai sus. Apoi in subgraful obtinut, se seteaza pe fiecare muchiie critica capacitatea 2, iar pe celelalte muchii se pune capacitatea 1. In graful obtinut, se cauta doua drumuri de crestere intre sursa si destinatie. Aceste drumuri constituie solutia problemei.

Sursa se gaseste in arhiva cu teste.

Download arhiva teste de intrare  

Click aici pentru a va intoarce

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