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:
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
// | |
// 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; | |
} |
Aqui está o código do problema usando o Algoritmo de Prim, para quem tiver curiosidade:
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 <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; | |
} |