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:
| // Noic – Avançado – Semana 55 – Problema 2 | |
| // O(M log M) | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 4e5+10; | |
| const long long inf = 1e18+10; | |
| typedef long long ll; | |
| struct E | |
| { | |
| int x, y; | |
| ll d; | |
| } aresta[maxn]; | |
| int pai[maxn], peso[maxn]; | |
| ll a[maxn]; | |
| // inicia o Union-Find para o Kruskal | |
| void Init(int n) | |
| { | |
| for (int i = 1; i <= n; i++) | |
| pai[i] = i, peso[i] = 1; | |
| } | |
| // funções do Union-Find | |
| int Find(int x) | |
| { | |
| if (pai[x] == x) return x; | |
| return pai[x] = Find(pai[x]); | |
| } | |
| void Join(int x, int y) | |
| { | |
| x = Find(x), y = Find(y); | |
| if (x == y) return; | |
| if (peso[x] < peso[y]) swap(x, y); | |
| pai[y] = x, peso[x] += peso[y]; | |
| } | |
| // comparador para ordenar as arestas pelos seus pesos | |
| bool comp(E a, E b) | |
| { | |
| return a.d < b.d; | |
| } | |
| int main(void) | |
| { | |
| int n, k; | |
| scanf("%d %d", &n, &k); | |
| int V; | |
| ll menor = inf; | |
| for (int i = 1; i <= n; i++) | |
| { | |
| scanf("%lld", &a[i]); | |
| if (a[i] < menor) | |
| menor = a[i], V = i; | |
| } | |
| int aux = 0; | |
| // insere todas as arestas de V para outro vértice | |
| for (int i = 1; i <= n; i++) | |
| if (i != V) | |
| aresta[++aux] = {V, i, menor + a[i]}; | |
| // arestas especiais | |
| for (int i = 1; i <= k; i++) | |
| { | |
| int u, v; | |
| ll w; | |
| scanf("%d %d %lld", &u, &v, &w); | |
| aresta[++aux] = {u, v, w}; | |
| } | |
| sort(aresta+1, aresta+aux+1, comp); | |
| Init(n); | |
| // menor custo | |
| ll ans = 0LL; | |
| for (int i = 1; i <= aux; i++) | |
| { | |
| if (Find(aresta[i].x) != Find(aresta[i].y)) | |
| { | |
| ans += aresta[i].d; | |
| Join(aresta[i].x, aresta[i].y); | |
| } | |
| } | |
| printf("%lld\n", ans); | |
| } |

Comente