Luogu P3366 【模板】最小生成树 题解

Luogu P3366 【模板】最小生成树 题解

题目描述

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

输入输出格式

输入格式:

第一行包含两个整数N、M,表示该图共有N个结点和M条无向边。(N<=5000,M<=200000)

接下来M行每行包含三个整数Xi、Yi、Zi,表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式:

输出包含一个数,即最小生成树的各边的长度之和;如果该图不连通则输出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

说明

时空限制:1000ms,128M

数据规模:

对于20%的数据:N<=5,M<=20

对于40%的数据:N<=50,M<=2500

对于70%的数据:N<=500,M<=10000

对于100%的数据:N<=5000,M<=200000

最小生成树板子题,没什么好说的……

算法说明:

以下两个算法都基于贪心实现。

kruskal算法采用并查集思想。步骤如下:

  1. 把每个点单独拆分,使得每个点的父亲都是它自己,即每个点单独成一个连通块。
  2. 每次取最短边,如果边两端的点处于同一个连通块,则pop掉,再取最短的边,直到边两端的点不处于同一个连通块为止。
  3. 合并两个点所在的连通块,并且ans+=两个点的距离。
  4. 重复2和3,共n-1遍。

prim算法采用遍历。步骤如下:

  1. 初始把1号点标记为已经使用过,并将与其相连的所有边加入队列。
  2. 每次取最短边,如果边的终点已使用过,则pop掉,再取最短的边,直到边的终点未使用过为止,
  3. 将边的终点标记为已经使用过,并且ans+=该边长度,再将与该边终点相连的所有边加入队列。
  4. 重复2和3,共n-1遍。
    *因为每次选择可用的新边时,该边起点都是已经使用过的(所以该边才有加入队列),所以只要判断该边终点即可。

代码:

kruskal算法:

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
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct edge{
int u,v,w;
};
int n,m,f[5010],v[5010];
priority_queue<edge,vector<edge>,greater<edge> >q;
bool operator >(const edge &a,const edge &b){
return a.w>b.w;
}
int find(int x){
if(x==f[x]) return x;
return f[x]=find(f[x]);
}
inline void join(int x,int y){
f[x]=y;
}
long long kruskal()
{
long long ans=0;
for(int x=1;x<n;x++)
{
edge temp=q.top();
while(find(temp.u)==find(temp.v))
{
q.pop();
temp=q.top();
}
q.pop();
int tu=find(temp.u),tv=find(temp.v);
join(tu,tv);
ans+=temp.w;
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) f[i]=i;
while(m--)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
v[x]=v[y]=1;
edge temp;
temp.u=x;
temp.v=y;
temp.w=z;
q.push(temp);
}
for(int i=1;i<=n;i++)
if(!v[i]){
cout<<"orz";
return 0;
}
cout<<kruskal();
return 0;
}

prim算法:

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<vector>
#include<queue>
using namespace std;
struct edge{
int v,w;
};
int n,m;
bool v[5010]={false};
vector<edge>G[5010];
priority_queue<edge,vector<edge>,greater<edge> >q;
bool operator >(const edge &a,const edge &b){
return a.w>b.w;
}
long long prim()
{
long long ans=0;
v[1]=1;
for(vector<edge>::iterator i=G[1].begin();i!=G[1].end();i++)
q.push(*i);
int x=1;
while(x++<n){
edge temp=q.top();
while(v[temp.v]){
q.pop();
temp=q.top();
}
ans+=temp.w;
v[temp.v]=1;
for(vector<edge>::iterator i=G[temp.v].begin();i!=G[temp.v].end();i++)
q.push(*i);
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
edge temp;
temp.v=y;
temp.w=z;
G[x].push_back(temp);
temp.v=x;
G[y].push_back(temp);
}
for(int i=1;i<=n;i++){
if(G[i].empty()){
cout<<"orz";
return 0;
}
}
cout<<prim();
return 0;
}

--It's the end.Thanks for your read.--