Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | apm.in, apm.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  dragus marius •mariusdrg |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Arbore partial de cost minim
Se da un graf conex bidirectionat G cu N noduri si M muchii cu cost. Se cere sa se aleaga un subgraf, care cuprinde toate nodurile,formeaza un arbore si acest arbore este de cost minim.
Date de intrare
Fisierul de intrare apm.in va contine pe prima linie numerele N si M, separate printr-un spatiu.Pe urmatoarele M randuri se vor gasi muchiile sub forma X,Y,C, cu semnificatia exista muchie intre X si Y cu costul C.
Date de ieşire
Fisierul de iesire apm.out va contine pe prima linie costul total minim.
Restricţii
- 1 ≤ N ≤ 200.000
- 1 ≤ M ≤ 400.000
- -1.000 ≤ C ≤ 1.000
- Pentru 20% din teste N,M ≤ 20
- Pentru inca 20% din teste N ≤ 800 si M ≤ 1.500.
Exemple
| apm.in | apm.out | apm.in | apm.out |
|---|---|---|---|
| 9 14 1 2 10 1 3 -11 2 4 11 2 5 11 5 6 13 3 4 10 4 6 12 4 7 5 3 7 4 3 8 5 8 7 5 8 9 4 9 7 3 6 7 11 | 37 | 3 3 1 2 -3 2 3 -4 3 1 -5 | -9 |
Explicatii
Exemplul 1:O solutie este sa se pastreze muchiile intre nodurile 7 si 3 cu costul 4,7 si 4 cu costul 5,7 si 9 cu costul 3,7 si 6 cu costul 11,9 si 8 cu costul 4,3 si 1 cu costul -11,1 si 2 cu costul 10,2 si 5 cu costul 11. Insumand costul 37. Solutia nu este neaparat unica.
Exemplul 2:Desi ar parea convenabil sa se introduca toate 3 muchiile, daca am face asta ar exista un ciclu si nu ar fi unic drumul dintre noduri.
Indicaţii de rezolvare
O prima idee ar fi cea mai evidenta, sa se aleaga prin backtracking muchiile care sa apartina Arborelui, dupa care se verifica prin un DFS conectivitatea arborelui. Aceasta rezolvare este cea mai naiva si are complexitate O(2N*N) si ar lua aproximativ 20 de puncte.
Presupunand ca sunt deja alese N - 2 muchii care nu formeaza cicluri, in alte cuvinte formeaza 2 arbori, si trebuie sa se mai aleaga inca o muchie, este evident ca trebuie sa se aleaga muchia minima care garanteaza conectivitatea arborilor. De la aceasta idee deducem ca cel mai bine ar fi sa adaugam muchii de cost minim, cat timp aceste muchii nu creaza cicluri.
Deci daca se sorteaza muchiile si se parcurg in ordinea sortarii, ne este mereu util sa bagam muchia minima cat timp aceasta nu creaza un cicluri. Aceasta solutie are complexitate O(N*M + Mlog2M), deoarece iterarea prin cele M muchii are complexitate O(M), iar parcurgerea dfs pentru verificarea ciclurilor este O(N). O astfel de solutie se poate vedea aici si ar trebui sa ia 40-50 de puncte, depinzand de implementare.
Parcurgerea dfs este redundanta, deoarece verificarea daca 2 noduri, cele pe care le leaga muchia, sunt in aceeasi grupa se poate face in O(log2N) cu multimi disjuncte. Astfel complexitatea se reduce la O(M*log2N + M*log2M) pentru ca se alege fiecare muchie si pentru fiecare muchie se verifica in O(log2N) utilitatea ei.Pentru o optimizare mai departe se pot apela diferite metode de sortare care se bazeaza pe inexactitatea reprezintarii numerelor in calculator. De obicei nu trebuie optimizata sortarea. O reprezentare grafica se poate gasi aici. Acest algoritm se numeste Kruskal si implementarea sa se poate vedea aici.
Pentru a intelege o alta solutie se presupune urmatorul scenariu: Existand deja calculat un subarbore minim vrem sa introducem in el inca un nod. Evident vom introduce nodul care are muchia minima care il leaga de subarborele deja format. Aceasta solutie are complexitate O(N*M), deoarece incepem cu un nod aleator si iterand tot adaugam inca cate un nod, pana sunt toate adaugate. Pentru a vedea nodul cu muchie minima parcurgem cele M muchii. Acest algoritm se poate optimiza, daca pentru fiecare nod se tine muchia minima curenta care il leaga de subarborele existent. La fiecare introducere a unui nod in subarbore, se actualizeaza toti vecinii lui.Aceasta solutie are complexitate O(N2) si ar trebui sa obitna 50 puncte.
Pentru a se optimiza mai departe algoritmul pentru extragerea minimului se foloseste un heap(data_structure) , iar de fiecare data cand se introduce un nod in subarbore sunt parcurse muchiile lui si actualizate nodurile. Astfel complexitatea devine O(M*log2N), o optimizare semnificativa fata de Kruskal, acest algoritm se numeste Prim. O sursa implementata se poate vedea aici.
