Programozás‎ > ‎Feladatok‎ > ‎

Minimális súlyú feszítőfa

A következő ábrán egy 7 csúcsú irányítatlan hálózat látható, amelyben az élek "súlyának" összege 243.

Ezt a hálózatot az alábbi mátrix is leírja: 

     A B C D E F G
A - 16 12 21 - - -
B 16 - - 17 20 - -
C 12 - - 28 - 31 -
D 21 17 28 - 18 19 23
E - 20 - 18 - - 11
F - - 31 19 - - 27
G - - - 23 11 27 -

Persze ha az a célunk, hogy a hálózat összefüggő legyen, de szeretnénk spórolni (az élek költsége a súlyuk), akkor több él is elhagyható úgy, hogy továbbra is összefüggő marad a hálózat. Például az alábbi részgráf súlya 93, ami 243-93=150 egységnyi megtakarítást jelent.



Feladat
Írjunk programot, ami adott gráfra megadja a maximálisan elérhető megtakarítást! (Feltehetjük, hogy a gráf összefüggő.)

Bemenet

A bemenet a hálózat fenti sémának megfelelő mátrixát tartalmazza, az elemeket vessző választja el. Az élek súly 1000-nél kisebb pozitív egész, a gráfnak legfeljebb 40 csúcsa van.

Kimenet

A kimenet egyetlen sorába a lehetséges maximális megtakarítás értékét kell írni, vagyis a törölhető élek összsúlyának maximumát.

Példa

Bemenet  Kimenet
-,16,12,21,-,-,-
16,-,-,17,20,-,-
12,-,-,28,-,31,-
21,17,28,-,18,19,23
-,20,-,18,-,-,11
-,-,31,19,-,-,27
-,-,-,23,11,27,-
150


Tesztadatok

network.txt  (40 csúcsa van) /Mivel ez a hivatalos P.E. feladata, nem írjuk ki a honlapra az eredményt./

Címkék

A feladat forrása: Project Euler 107. feladat
Algoritmusok: minimális súlyú feszítőfa, MST