Module: Gestrandete Bäume: Der Kruskala-Algorithmus


Problem

1/4

Kruskals Algorithmus: Der Anfang

Theory Click to read/hide

Beispiel für den minimalen Rest des Holzes mit vorgegebenen Rippengewichten:


Algorithm Kruscal:

(1) Wir reißen die Rippen nach Maß.
(2) Wir bilden eine Liste mit n Bäumen.
(3) Beginnen Sie den Prozess der Integration dieser Bäume in den minimalen Restbaum:
Alle Rippen müssen entfernt werden, und wenn die Stromrippen unterschiedliche Auflagen haben, muss der Träger kombiniert werden.
(4) Am Ende aller Rippen werden alle Spitzen zu demselben Träger gehören.

Problem

Es ist erforderlich, einen Baum mit minimalem Gewicht in der verknüpften Grafik zu finden.
 
Eingabeformat:
 
Die erste Zeile der Eingabedatei enthält zwei natürliche Zahlen N, M ist die Anzahl der Scheitelpunkte bzw. der Kanten des Graphen. Die folgenden m Zeilen enthalten eine Beschreibung der Kanten nacheinander pro Zeile. Die Nummer i wird durch die drei natürlichen Zahlen Bi, Ei, Wi die Endnummern der Kante und ihr Gewicht entsprechend beschrieben (1 <= Bi, Ei <= N, 0 <= Wi <= 232-1. N <= 10, M <= 10).
 
Ausgabeformat:
 
Die einzige Zeile der Ausgabedatei muss eine natürliche Zahl enthalten - das Gewicht des minimalen Rahmenbaums. 
 
Eingabe Ausgabe
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!