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.

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

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.

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.

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

A feladat forrása: Project Euler 107. feladat

Algoritmusok: minimális súlyú feszítőfa, MST