Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-12-18 17:15:14.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:apm.in, apm.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată demariusdrgdragus marius mariusdrg
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Arbore partial de cost minim

Se da un graf conex neorientat G cu N noduri si M muchii, fiecare muchie avand asociat un cost. Se cere sa se determine un subgraf care cuprinde toate nodurile si o parte din muchii, astfel incat subgraful determinat sa aiba structura de arbore si suma costurilor muchiilor care il formeaza sa fie minim posibila. Subgraful cu proprietatile de mai sus se va numi arbore partial de cost minim pentru graful dat.

Date de intrare

Fisierul de intrare apm.in va contine pe prima linie numerele N si M, separate printr-un spatiu. Pe urmatoarele M linii se vor gasi muchiile grafului sub forma X Y C, cu semnificatia ca exista muchie neorientata intre X si Y de cost C.$

Date de ieşire

Fisierul de iesire apm.out va contine pe prima linie costul arborelui partial de cost 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.inapm.outapm.inapm.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
373 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.

Aplicatii

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?