Module: 生成树：Kruskal 算法


Problem

1/4

克鲁斯卡尔算法：开端

Theory Click to read/hide

具有指定边权重的图中最小生成树的示例： 


克鲁斯卡尔算法：

1) 按权重对边进行排序 以非递减顺序。
2) 我们形成一个 n 棵树的列表（每个顶点都是一棵树）。
3) 我们开始将这些树组合成最小生成树的过程：
     遍历所有边，如果当前边的两端属于不同的子树，则合并这些子树。
4) 在所有边的枚举结束时，所有的顶点将属于同一个子树。

Problem

<分区> 要求在连通图中找到最小权重生成树。
<分区>  
<分区> 输入数据格式：
<分区>  
<分区> 输入文件的第一行包含两个自然数 N，M——分别是图的顶点数和边数。接下来的 m 行包含边的描述，每行一个。边数i由三个自然数Bi、Ei、Wi描述，分别为边的端点及其权重（ 1 <= Bi, Ei <= N, 0 <= Wi <= 232< /sup>-1.N <= 10, M <= 10).
<分区>  
<分区> 输出格式：
<分区>  
<分区> 输出文件的唯一一行应该包含一个自然数——最小生成树的权值。 
<分区>  
<分区> <正文>

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++
输入 输出
<分区> 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!