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 bidirectionat G cu N noduri si M muchii cu cost. Se cere sa se aleaga o submultime de muchii dintre aceste M, de cost minim, astfel incat sa existe un singur drum intre oricare doua noduri parcurgand doar muchii din submultimea aleasa.
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 ≤ 200.000
- Pentru 20% din teste N,M ≤ 20
- Pentru inca 30% din teste N,M ≤ 5.000
- Intre oricare doua noduri va exista decat o muchie.
Exemplu
| 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 |
Explicaţie
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. Tin sa mentionez ca solutia nu este unica.
| apm.in | apm.out |
|---|---|
| 3 3 1 2 -3 2 3 -4 4 1 -5 | -9 |
