Solução Árvore Geradora Máxima

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.

	#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;
	}

view raw

mst.cpp

hosted with ❤ by GitHub