Interneto paslaugų tiekėjas nori sukurti naują tinklą. Septyni miestai turėtų būti sujungti taip, kad kiekvienas miestas galėtų siųsti ir gauti pranešimus vienas iš kito.

Įmonė, norėdama sukurti ryšius tarp miestų, turi sumokėti tam tikrą pinigų dalį. Kainos nurodytos ant linijų, jungiančių miestus.

Kuriuos ryšius įmonė turėtų sukurti, kad kaina būtų mažiausia?