最小生成树笔记

• 生成树：删去一些边，使图变成树。

  对于 $n$ 个点的图，生成树有 $n-1$ 条边。

• 最小生成树：所有生成树中边权最小的。

• 对于一个图，不存在最大/最小生成树的条件是并查集里面没有 $n$ 个点，即总边数 $<n-1$。

• 如果一个图存在唯一最小生成树，需要满足对于所有非最小生成树中的边，对于起点和终点 $u$、$v$，边 $u\to v$ 的边权大于 $u$、$v$ 在最小生成树上的最短距离的最大边权。

最小生成树算法

Prim

不会。堆优化后时间复杂度为 $O(m\log n)$。

Kruskal

1. 将所有边按边权升序排列。
2. 依次考虑所有边，如果边的两端在不同连通块内，将该边加入生成树，合并连通块。

• 用并查集维护连通块关系。

时间复杂度为 $O(m\log m)$。

for(int i=1;i<=m&&cnt<n-1;i++)
{
    int x=e[i].from,y=e[i].to,z=e[i].w;
    int u=find(x),v=find(y);
    if(u==v) continue;
    fa[u]=v;cnt++;
    add(x,y,z);add(y,x,z);
}
1
2
3
4
5
6
7
8

---

练手板子题

代码如下：

#include 
using namespace std;

int to[500000],v[500000],father[500000],nxt[500000],cnt,head[500000],uu,vv,ans,M,N;

int find(int x)
{
	if(father[x]!=x) father[x]=find(father[x]);
	return father[x];
}

struct node
{
	int to,from,v;
}gg[500000];

bool cmp(node a,node b)
{
	return a.v<b.v;
}

int main()
{
	cin>>N>>M;
	int sum;
	for(int i=1;i<=N;i++) father[i]=i;
	for(int i=1;i<=M;i++) cin>>gg[i].from>>gg[i].to>>gg[i].v;
	sort(gg+1,gg+1+M,cmp);
	for(int i=1;i<=N;i++) father[i]=i;
	for(int i=1;i<=M&&cnt<N-1;i++)
	{
		int uu=find(gg[i].from),vv=find(gg[i].to);
		if(uu!=vv)
		{
			sum+=gg[i].v;
			father[uu]=vv;
			cnt++;
		}
	}
	if(cnt!=N-1)
		cout<<"orz";
	else
		cout<<sum;
	return 0;
}
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