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á 
arestas possíveis no grafo, esta solução não é eficiente.
Seja 
o vértice no grafo como menor valor 
. 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 para todos os outros vértices do grafo. Além disso, podemos utilizar algumas das 
arestas especiais.
Com isso, a solução será bastante parecida com a anterior: Vamos inserir todas as 
arestas que ligam o vértice 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á 
, que é a mesma complexidade do Algoritmo de Kruskal. Confira o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 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); | |
| } |