什么是最小生成树？

  • 在一个有$n$个点，$m$条边的无向连通图中，已知各边的权值，现在我们要删去一些边，保留一些边，使得图仍然保持连通，求保留边的边权之和的最小值

Kruskal算法

算法原理

​ Kruskal算法的基本算法是贪心，即从小到大加入每一条边

前置知识

​ 快速排序，结构体存图，并查集

实现思路&贪心正确性

​ 利用贪心的思想，将所有边根据边权从小到大排序，然后如果当前这条边所连接的两个结点不连通，就把这条边加进来，这样就可以保证，在使两个结点保持联通的过程中所增加的边的边权是最小的，QED。

实现技巧

​ 排序使用$sort$，判断结点是否联通以及加边用并查集实现

Code

模板题，洛谷P3366

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=2e5+10;
int p[N];
struct edge{
	int x,y,c;
}a[M];
int find(int x)
{
	if(x!=p[x])
	{
		p[x]=find(p[x]);
	}
	return p[x];
}
void merge(int i,int j)
{
	p[find(i)]=find(j);
}
bool cmp(edge q,edge p)
{
	return q.c<p.c;
}
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		p[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].c;
		merge(a[i].x,a[i].y);
	}
	for(int i=1;i<n;i++)
	{
		if(find(i)!=find(i+1))
		{
			cout<<"orz"<<endl;
			return 0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		p[i]=i;
	}
	sort(a+1,a+m+1,cmp);
	int ans=0,sum=0;
	for(int i=1;i<=m;i++)
	{
		if(find(a[i].x)!=find(a[i].y))
		{
			merge(a[i].x,a[i].y);
			sum++;
			ans+=a[i].c;
		}
		if(sum==n-1)
		{
			break;
		}
	}
	cout<<ans<<endl;
	return 0;
}

简单练习题

P1195 口袋的天空

SCOI2005 繁忙的都市