Totusi niciuna dintre aceste variante nu se incadreaza in timp pentru limitele date, asa ca propunem urmatorul algoritm, avand complexitatea $O(N^2^ + K * N)$. Prima data se gaseste arborele partial de cost minim pentru graful initial, folosind algoritmul Prim. Pentru urmatorii $K$ pasi avem doua posibilitati:
# Muchia curenta este intre doua noduri din arborele partial minim actual. Daca muchia are lungime mai mica, suprascriem muchia din arbore si costul arborelui se imbunatateste cu diferenta costurilor. Daca muchia are lungime mai mare sau egala, arborele ramane neschimbat.

# Muchia nu face parte din arbore. Fiindca arborele are numar maxim de muchii din punctul de vedere al aciclitatii, o noua muchie va forma cu siguranta un ciclu. Pentru a ajunge iarasi la un arbore, din acest ciclu trebuie sters o muchie. Pentru ca arborele care rezulta sa aiba cost minim, vom sterge muchia cu cost maxim din ciclu.

# Muchia nu face parte din arbore. Fiindca arborele are numar maxim de muchii din punctul de vedere al aciclitatii, o noua muchie va forma cu siguranta un ciclu. Pentru a ajunge iarasi la un arbore, din acest ciclu trebuie stearsa o muchie. Pentru ca arborele care rezulta sa aiba cost minim, vom sterge muchia cu cost maxim din ciclu.