|
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 |