NézetNyomtat

Hálózat (Megoldás)
Címkék > Feladat
Elmélet > Algoritmusok > Mohó
Elmélet > Algoritmusok > Rendezések

Hálózat

A feladat

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:

Bemenet

A bemeneti fájl első sorában a városok száma N (5<=N<=100) szerepel. A további $\frac{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