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.
Cosmin: chestia cu un singur drum e o proprietate a arborelui nu e un lucru ce defineste arborele. Cred ca pe wikipedia gasesti definitii mai bune a arborelui partial de cost minim. http://en.wikipedia.org/wiki/Minimum_spanning_tree
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
- Pentru 20% din teste N,M ≤ 20
- Pentru inca 30% din teste N,M ≤ 5.000
- Intre oricare doua noduri va exista maxim o muchie.
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 ni s-ar parea convenabil sa introducem toate 3 muchiile , daca am face asta ar exista un ciclu si nu ar fi unic drumul dintre noduri.
