L'albero che si spanna mimimum con un vincolo sul numero di alcuni tipi di bordi

Question

Ho il seguente problema.

Supponiamo che abbiamo un grafico $ g = (v, e) $ in cui tutti $ e in e $ hanno un peso positivo e $ e $ può essere separato in due set disgiunti $ e = a coppa b $. Dobbiamo trovare un albero da spanning in modo tale che minimizziamo il peso totale, ma possiamo anche usare solo un massimo di $ C $ i bordi in $ b $.

Sento che questo è solo Prim/Kruskal con ulteriori condizioni nella condizione principale se, ma è corretto? Penso che possiamo ancora usare un algoritmo avido ma non sappiamo come mostrare la correttezza.