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