Module: Cây bao trùm: Thuật toán Kruskal


Problem

1/4

Thuật toán của Kruskal: Sự khởi đầu

Theory Click to read/hide

Ví dụ về cây bao trùm tối thiểu trong biểu đồ có trọng số cạnh được chỉ định: 


Thuật toán Kruskal:

1) Sắp xếp các cạnh theo trọng lượng  theo thứ tự không giảm.
2) Lập danh sách n cây (mỗi đỉnh là một cây).
3)  Chúng tôi bắt đầu quá trình kết hợp các cây này thành một cây bao trùm tối thiểu:
      tất cả các cạnh đều được duyệt qua và nếu các đầu của cạnh hiện tại thuộc về các cây con khác nhau, thì các cây con này sẽ được hợp nhất.
4) Khi kết thúc phép liệt kê tất cả các cạnh, tất cả các đỉnh sẽ thuộc về cùng một cây con.

Problem

Cần phải tìm một cây bao trùm có trọng số tối thiểu trong biểu đồ liên thông.
 
Định dạng dữ liệu đầu vào:
 
Dòng đầu tiên của file input chứa 2 số tự nhiên N, M - lần lượt là số đỉnh và số cạnh của đồ thị. m dòng tiếp theo chứa mô tả các cạnh, mỗi dòng một cạnh. Số cạnh i được mô tả bằng ba số tự nhiên Bi, Ei, Wi tương ứng là điểm cuối của cạnh và trọng số của nó ( 1 <= B< sub>i, Ei <= N, 0 <= Wi <= 232< /sup>-1.N <= 10, M <= 10).
 
Định dạng đầu ra:
 
Dòng duy nhất của tệp đầu ra phải chứa một số tự nhiên - trọng số của cây bao trùm tối thiểu. 
 

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++
Nhập Đầu ra
4 4
1 2 1
2 3 2
3 4 5
4 1 4
7
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!