Module: Árboles de expansión: Algoritmo de Kruskal


Problem

1/4

Algoritmo de Kruskal: el comienzo

Theory Click to read/hide

Un ejemplo de un árbol de expansión mínimo en un gráfico con pesos de borde especificados: 


Algoritmo de Kruskal:

1) Ordenar bordes por peso  en orden no decreciente.
2) Formamos una lista de n árboles (cada vértice es un árbol).
3) Comenzamos el proceso de combinar estos árboles en un árbol de expansión mínimo:
      todos los bordes se recorren, y si los extremos del borde actual pertenecen a diferentes subárboles, estos subárboles se fusionan.
4) Al final de la enumeración de todas las aristas, todos los vértices pertenecerán al mismo subárbol.

Problem

Es necesario encontrar un árbol de expansión de peso mínimo en un gráfico conectado.
 
Formato de datos de entrada:
 
La primera línea del archivo de entrada contiene dos números naturales N, M, el número de vértices y aristas del gráfico, respectivamente. Las siguientes m líneas contienen la descripción de los bordes, una por línea. El número de arista i se describe mediante tres números naturales Bi, Ei, Wi los extremos de la arista y su peso, respectivamente ( 1 <= Bi, Ei <= N, 0 <= Wi <= 232< /sup>-1. N <= 10, M <= 10).
 
Formato de salida:
 
La única línea del archivo de salida debe contener un número natural: el peso del árbol de expansión mínimo. 
 
Entrar Salida
4 4
1 2 1
2 3 2
3 4 5
4 1 4 7

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct edge
{
	int l,a,b;
};

bool cmp(const edge &a, const edge &b)
{
    return a.l < b.l;
}

int main()
{
	int m, n;
	cin >> n >> m;

	vector < edge > g(m);

	for (int i = 0; i < m; i++)
	{
		int a, b, l;
		cin >> a >> b >>l;
		edge e;
                e.l = l; e.a= a-1; e.b = b-1;
		g[i] = e;
	}
	long long cost = 0;
	vector < pair<int, int> > res;

	sort(g.begin(), g.end(),cmp);
	vector<int> tree_id(n);
	for (int i = 0; i < n; ++i)
		tree_id[i] = i;
	for (int i = 0; i < m; ++i)
	{
		int a = g[i].a, b = g[i].b, l = g[i].l;
		if (tree_id[a] != tree_id[b])
		{        
			res.push_back(make_pair(a, b));
			int old_id = tree_id[b], new_id = tree_id[a];
			for (int j = 0; j < n; ++j)
				if (tree_id[j] == old_id)
					tree_id[j] = new_id;
		}
	}

	cout << cost;
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!