Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-12-07 16:07:29.
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 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.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
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.inapm.out
3 3
1 2 -3
2 3 -4
4 1 -5
-9

Explicaţie
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.

Indicaţii de rezolvare

Aplicatii

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?