最小生成树

最小生成树

最小生成树

Prim算法

朴素Prim

O(n^2)

步骤:

  1. 初始化:把每个点到集合的距离设为正无穷
  2. 每次找到集合外距离最近的点u
  3. 用u来更新其它点到 集合 的距离(Dijkstra中,更新的是到起点的距离)

acwing 858

(其实就是把下面那道洛谷模板题的数据换成稠密图)

(1≤n≤500, 1≤m≤10^5)

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=510;
const int inf=0x3f3f3f3f;
int n,m;
int in[N],dis[N],g[N][N];
int ans=0,flag=0;
void prim()
{
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!in[j] and (t==-1 or dis[t]>dis[j]))
{
t=j;
}
}
if(i>1 and dis[t]==inf)flag=1;
if(flag)break;
if(i>1)ans+=dis[t];
for(int j=1;j<=n;j++)
{
dis[j]=min(dis[j],g[t][j]);
}
//更新这个点连的其他点到集合的距离
//这里的dis表示这个点到集合的距离

in[t]=1;
}
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m;
memset(g,0x3f,sizeof(g));
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
g[u][v]=g[v][u]=min(g[u][v],w);
}
prim();
if(flag)cout<<"impossible";
else cout<<ans;
return 0;
}

堆优化Prim算法(不常用,类似Dijkstra)

O(m logn)

Kruskal 算法

O(m logm)

步骤:

  1. 将所有边按权值从小到大排序,时间复杂度O(m logm)
  2. 枚举每条边 u-v (权w)。如果u,v不连通,就将这条边加入集合中。(并查集)

洛谷P3366 【模板】最小生成树

题目描述

如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz

输入格式

第一行包含两个整数 N,MN,M,表示该图共有 NN 个结点和 MM 条无向边。

接下来 MM 行每行包含三个整数 X_i,Y_i,Z_i,表示有一条长度为 Z_i 的无向边连接结点 X_i,Y_i。

输出格式

如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz

输入输出样例

输入 #1

1
2
3
4
5
6
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出 #1

1
7

代码

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200050;
struct node
{
int u,v,w;
}e[N];
int n,m;
int fa[N];
int cnt=0,res=0,tot=0;
void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].u=u;
e[cnt].w=w;
}
bool cmp(node a,node b)
{
return a.w<b.w;
}
int find(int x)
{
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
}
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
for(int i=1;i<=m;i++)
{
int u=e[i].u,v=e[i].v,w=e[i].w;
u=find(u),v=find(v);
if(u!=v)
{
res+=w;
tot++;
fa[u]=v;
}
}
if(tot<n-1)cout<<"orz";
else cout<<res;
return 0;
}