Solução de Roger Benet, comentários de João Guilherme
Para ver o problema original, clique aqui.
Esse problema é uma adaptação do problema clássico de achar a árvore geradora mínima, no curso Noic temos uma explicação de um algoritmo popular para resolver tal problema (para vê-lo clique aqui).
Assim usamos apenas uma versão adaptada do algoritmo de Kruskal. Primeiro ordenamos as arestas pelo seus pesos, depois começando do final do vetor, onde temos a aresta mais pesada, checamos se os vértices ligados por essa aresta já fazem parte da mesma árvore, se eles fizerem nós seguimos em frente para evitar ciclos, se eles não fizerem nós os ligamos e somamos o peso dessa aresta ao custo total.
Segue 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
#include <bits/stdc++.h> | |
using namespace std; | |
const int MAX = 1e5 + 10; | |
pair <int, pair <int,int> > p[MAX]; | |
int id[MAX], vertices, arestas, testes, ans; | |
int root(int x){ | |
while(id[x] != x){ | |
id[x] = id[id[x]]; | |
x = id[x]; | |
} | |
return x; | |
} | |
void init(int n){ | |
for(int i = 1; i <= n; i++) | |
id[i] = i; | |
} | |
void join(int a, int b){ | |
a = root(a); | |
b = root(b); | |
id[a] = b; | |
} | |
int main(){ | |
scanf("%d", &testes); | |
while(testes--){ | |
scanf("%d %d", &vertices, &arestas); | |
for(int i = 0; i < arestas; i++){ | |
int a,b,c; | |
scanf("%d %d %d", &a, &b, &c); | |
p[i] = make_pair(c, make_pair(a,b)); | |
} | |
init(vertices); | |
sort(p,p+arestas); | |
ans = 0; | |
for(int i = arestas-1; i > -1; i--){ | |
int x = p[i].second.first; | |
int y = p[i].second.second; | |
int cost = p[i].first; | |
if(root(x) != root(y)){ | |
ans += cost; | |
join(x,y); | |
} | |
} | |
printf("%d\n",ans); | |
} | |
return 0; | |
} |