Vizualizare soluţie
Titlul problemei: | flood |
Numărul problemei: | 2 |
Runda: | Runda #6 - concurs |
Soluţie: | Putem
asocia problemei un graf in care varfurile grafului sunt localitatile
si drumurile existente intre localitati sunt muchiile. Problema cere sa obtinem un graf conex adaugand muchii dintr-o multime specificata, astfel incat costul total al muchiilor adaugate sa fie minim.
1. Vom citi drumurile existente si vom retine evidenta componentelor conexe folosind reprezentarea multimilor disjuncte cu ajutorul arborilor si algoritmi Union-Find. 2. Vom organiza drumurile care trebuie sa fie reconstruite ca un min-heap. 3. Vom completa graful, printr-un procedeu similar cu algoritmul lui Kruskal. Cat timp graful nu este conex, vom selecta o muchie de cost minim care nu formeaza cicluri cu muchiile deja selectate.
Datorita dimensiunii f. mari a fisierelor de intrare in arhiva de teste nu se afla toate fisierele de intrare. Arhiva de teste poate fi obtinuta la cerere prin e-mail (10 MB). |