Module: امتداد الأشجار: خوارزمية Kruskal


Problem

1/4

خوارزمية Kruskal: البداية

Theory Click to read/hide

مثال على الحد الأدنى من الشجرة الممتدة في رسم بياني بأوزان حواف محددة: & nbsp؛


خوارزمية Kruskal:

1) فرز الحواف حسب الوزن نبسب ؛ بترتيب غير تنازلي.
2) نشكل قائمة من عدد n من الأشجار (كل رأس عبارة عن شجرة).
3) نبسب ؛ نبدأ عملية دمج هذه الأشجار في الحد الأدنى من الشجرة الممتدة:
نبسب ؛ نبسب ؛ نبسب ؛ يتم اجتياز جميع الحواف ، وإذا كانت أطراف الحافة الحالية تنتمي إلى أشجار فرعية مختلفة ، فسيتم دمج هذه الأشجار الفرعية.
4) على & nbsp ؛ في نهاية تعداد جميع الحواف ، ستنتمي جميع الرؤوس إلى نفس الشجرة الفرعية.

Problem

مطلوب للعثور على حد أدنى للوزن يمتد في الرسم البياني المتصل.
نبسب ؛
تنسيق بيانات الإدخال :
نبسب ؛
يحتوي السطر الأول من ملف الإدخال على رقمين طبيعيين N ، M - عدد رؤوس وحواف الرسم البياني ، على التوالي. تحتوي سطور m التالية على وصف للحواف ، واحد لكل سطر. يتم وصف رقم الحافة i بثلاثة أرقام طبيعية B i و E i و W i ونقاط نهاية الحافة ووزنها على التوالي ( 1 & lt؛ = B i ، E i & lt؛ = N، 0 & lt؛ = W i & lt؛ = 2 32 < / sup> -1. N & lt؛ = 10، M & lt؛ = 10).
نبسب ؛
تنسيق الإخراج :
نبسب ؛
يجب أن يحتوي السطر الوحيد من ملف الإخراج على رقم طبيعي واحد - وزن الحد الأدنى للشجرة الممتدة. & nbsp؛
نبسب ؛
<الجسم>
أدخل الإخراج
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!