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.
![]()
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ő.)
BemenetA 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.
KimenetA 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
Tesztadatok
CímkékA feladat forrása: Project Euler 107. feladat
Algoritmusok: minimális súlyú feszítőfa, MST
|
Programozás > Feladatok >