Solução por Lúcio Cardoso
Uma possível solução seria a seguinte: Inserimos no grafo todas as possíveis arestas ligando um par de vértices qualquer (com seus respectivos custos) e todas as arestas especiais. Após isso, utilizaremos o Algoritmo de Kruskal para encontrar a MST (Árvore geradora mínima) do grafo. O custo da MST será a resposta.
No entanto, como há $$O(n^2)$$ arestas possíveis no grafo, esta solução não é eficiente.
Seja $$v$$ o vértice no grafo como menor valor $$a$$. Perceba que não precisamos de todas as arestas possíveis do grafo – as únicas arestas que serão úteis são aquelas que ligam o vértice $$v$$ para todos os outros vértices do grafo. Além disso, podemos utilizar algumas das $$k$$ arestas especiais.
Com isso, a solução será bastante parecida com a anterior: Vamos inserir todas as $$N-1$$ arestas que ligam o vértice $$v$$ com qualquer outro vértice do grafo e, também, as arestas especiais. A resposta do problema será o custo da MST deste grafo, já que queremos que o ele seja conexo com o menor custo possível.
A complexidade final será $$O(M \log{}M)$$, que é a mesma complexidade do Algoritmo de Kruskal. Confira o código para melhor entendimento:
https://gist.github.com/luciocf/5cc8704030fa9852a429ed234f49aa66
Deixe um comentário