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.
BemenetA 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.
KimenetA kimenetre hálózat kiépítéséhez szükséges minimális összköltséget kell kiírni.
Tesztadatok
CímkékA feladat forrása: Tihanyi Balázs feladata
Algoritmusok: minimális összsúlyú feszítőfa
megoldás |
Programozás > Feladatok >