Solução Reduzindo Detalhes em um Mapa - Semana 1

Solução por Lucca Siaudzionis

Este problema é um clássico que consiste em: dado um grafo, encontrar sua Árvore Geradora Mínima (mais conhecida pelo nome, em inglês, Minimum Spanning Tree ou MST). Há dois algoritmos muito conhecidos para resolver esse tipo de problema:

Eu, por preferência pessoal, uso o Algoritmo de Kruskal, e aqui está meu código no problema:

	//
	// reduzindo_detalhes_em_um_mapa.cpp
	// programas2
	//
	// Created by Lucca Siaudzionis on 24/02/13.
	// Copyright (c) 2013 Luccasiau. All rights reserved.
	//

	#include <cstdio>
	#include <algorithm>
	#define MAXN 510
	#define MAXM 124755
	using namespace std;

	int nodes,arestas;
	int pai[MAXN];
	int peso[MAXN];

	int find(int x){ // função do Union Find
	if( pai[x] == x ) return x;
	return pai[x] = find(pai[x]);
	}

	int join(int a,int b){ // função do Union Find
	a = find(a);
	b = find(b);

	if(peso[a] < peso[b]) pai[a] = b;
	else if(peso[b] < peso[a]) pai[b] = a;
	else{
	pai[a] = b;
	peso[b]++;
	}

	}

	struct tipo_aresta{
	int x;
	int y;
	int dis;
	};

	bool comp(tipo_aresta a, tipo_aresta b){ // função para ordenação
	return a.dis < b.dis;
	}

	tipo_aresta edges[MAXM];

	int main(){

	scanf("%d %d",&nodes,&arestas);

	for(int i = 1;i<=nodes;i++) pai[i] = i;

	for(int i = 1;i<=arestas;i++){
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	edges[i].x = a;
	edges[i].y = b;
	edges[i].dis = c;
	}

	sort(edges+1,edges+arestas+1,comp); // ordenar as arestas em ordem crescente
	int resp = 0;

	for(int i = 1;i<=arestas;i++){

	// só se usa uma arestas se seus dois vértices
	// estiverem em componentes distintas

	if(find(edges[i].x) != find(edges[i].y)){
	resp += edges[i].dis;
	join(edges[i].x, edges[i].y);
	}

	}

	printf("%d\n",resp);

	return 0;
	}

view raw

reduzindo_detalhes_em_um_mapa.cpp

hosted with ❤ by GitHub

Aqui está o código do problema usando o Algoritmo de Prim, para quem tiver curiosidade:

	#include <cstdio>

	#define MAXN 1010
	#define INF 999999999

	#define min(A,B) ((A)<(B))?(A):(B)

	//Globais-------------
	int n,m;
	int marcado[MAXN];
	int grafo[MAXN][MAXN];
	//--------------------

	void prim(int v){
	marcado[v] = 1;

	while(1){
	int davez = -1, menor = INF;

	for(int i=1;i<=n;i++)
	if( grafo[v][i] < menor && !marcado[i] ){
	menor = grafo[v][i];
	davez = i;
	}

	if( davez == -1 ) break;

	marcado[davez] = 1;

	for(int i=1;i<=n;i++)
	if( !marcado[i] )
	grafo[v][i] = min(grafo[v][i],grafo[davez][i]);
	}
	}

	int main(){

	scanf("%d %d", &n,&m);

	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) grafo[i][j] = INF;

	for(int i=1;i<=m;i++){
	int a,b,c;

	scanf("%d %d %d", &a,&b,&c);

	grafo[a][b] = grafo[b][a] = c;
	}

	prim(1);

	int soma = 0;
	for(int i=2;i<=n;i++) soma += grafo[1][i];

	printf("%d\n", soma);

	return 0;
	}

view raw

reduzindo_detalhes_em_um_mapa_Prim.cpp

hosted with ❤ by GitHub