Programozás‎ > ‎Feladatok‎ > ‎

Hálózat

Bergengóciában a technika fejlődésével az emberek szeretnék neten megosztani egymással a érdekes matematikai rejtvényeket, s létrehoznának egy olyan számítógépes hálózatot, amelyben mindenki el tudja juttatni a feladatát az összes többi városban élő embernek.
Bármely két várost összeköthetünk egy bizonyos költség árán. A feladatunk megtalálni azt a minimális költségű hálózatot, amelyben minden város összeköttetésben áll a többivel.

Példa a költségekre és a minimális költségű hálózatra:
 

Feladat

Írjunk programot, ami meghatározza a minimális összköltségű hálózat árát.

Bemenet

A bemeneti fájl első sorában a városok száma N (5<=N<=100) szerepel. A további N(N-1)/2 sor mindegyikében három adat van (szóközzel elválasztva): két város sorszáma és a két város közötti hálózat kiépítési K (1<=K<=200) költsége. 

Kimenet

A kimenetre hálózat kiépítéséhez szükséges minimális összköltséget kell kiírni.

Tesztadatok

halozat.zip ( javítva )

Címkék

A feladat forrása: Tihanyi Balázs feladata
Algoritmusok: minimális összsúlyú feszítőfa

megoldás