Asadar, problema ramasa este aceea de a alege cele mai mari {$K-(N-1)$} muchii avand ambele capete in multimea {${1,2,..,N-1}$}. Doua variante simple au complexitate $O(N*K)$ si {$O(K*logN)$}, insa vor depasi limita de timp.

O solutie acceptabila ar consta in a cauta binar valoarea celei mai mici muchii din cele $K-(N-1)$ pe care mai dorim sa le alegem si sa calculam in $N*logN$ cate perechi de noduri au costul mai mare sau egal cu valoarea fixata in cautarea binara. Vom alege cea mai mare valoare pentru care exista {$X >= K-(N-1)$} muchii cu cost mai mare sau egal cu ea.

O solutie acceptabila ar consta in a cauta binar valoarea celei mai mici muchii din cele $K-(N-1)$ pe care mai dorim sa le alegem si sa calculam in $O(N)$ cate perechi de noduri au costul mai mare sau egal cu valoarea fixata in cautarea binara. Vom alege cea mai mare valoare pentru care exista {$X >= K-(N-1)$} muchii cu cost mai mare sau egal cu ea.

 Daca {$X=K-(N-1)$}, am gasit muchiile cautate. Daca $X>K-(N-1)$ este din cauza ca exista prea multe muchii cu acelasi cost maxim gasit. In aceasta situatie, putem scadea din costul total al muchiilor gasite {$costul_maxim_gasit * (X - (K - (N-1)))$} pentru a obtine costul total al celor mai mari $K-(N-1)$ muchii.
Solutia finala afisata va fi {$CK + 2 * (suma_totala_a_costurilor_muchiilor - CK)$}, unde $CK$ a fost definit anterior. Complexitatea algoritmului este {$O(N * log(N) * log(CMAX))$}.