最小生成树的两种方法：Prim和Kruskal。
Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。Prim是以更新过的节点的连边找最小值，Kruskal是直接将边排序。
Prim
Prim的思想是将任意节点作为根，再找出与之相邻的所有边（用一遍循环即可），再将新节点更新并以此节点作为根继续搜，维护一个数组：dis，作用为已用点到未用点的最短距离。
说的再通俗一点，每次都循环，把最低的距离的那个点能到的点的距离给更新了，直到不能更新为止。
直接上堆优化罢（）
有一种迪杰斯特拉的美感
【模板】最小生成树
题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出
orz。
输入格式
第一行包含两个整数 \(N,M\)，表示该图共有 \(N\) 个结点和 \(M\) 条无向边。
接下来 \(M\) 行每行包含三个整数
\(X_i,Y_i,Z_i\)，表示有一条长度为 \(Z_i\) 的无向边连接结点 \(X_i,Y_i\)。
输出格式
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出
orz。
样例 #1
样例输入 #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
提示
数据规模：
对于 \(20\%\) 的数据，\(N\le 5\)，\(M\le
20\)。
对于 \(40\%\) 的数据，\(N\le 50\)，\(M\le
2500\)。
对于 \(70\%\) 的数据，\(N\le 500\)，\(M\le 10^4\)。
对于 \(100\%\) 的数据：\(1\le N\le 5000\)，\(1\le M\le 2\times 10^5\)，\(1\le Z_i \le 10^4\)。
样例解释：
所以最小生成树的总边权为 \(2+2+3=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
| #include<bits/stdc++.h>
using namespace std;
const int N=5005;
int k,n,m,cnt,sum,ai,bi,ci,head[N],dis[N],vis[N];
struct Edge
{
int v,w,next;
}e[400005];
void add(int u,int v,int w)
{
e[++k].v=v;
e[k].w=w;
e[k].next=head[u];
head[u]=k;
}
typedef pair <int,int> pii;
priority_queue <pii,vector<pii>,greater<pii> > q;
void prim()
{
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty()&&cnt<n)
{
int d=q.top().first,u=q.top().second;
q.pop();
if(vis[u]) continue;
cnt++;
sum+=d;
vis[u]=1;
for(int i=head[u];i!=-1;i=e[i].next)
if(e[i].w<dis[e[i].v])
{
dis[e[i].v]=e[i].w;
q.push(make_pair(dis[e[i].v],e[i].v));
}
}
}
int main()
{
memset(dis,127,sizeof(dis));
memset(head,-1,sizeof(head));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>ai>>bi>>ci;
add(ai,bi,ci);
add(bi,ai,ci);
}
prim();
if (cnt==n)cout<<sum;
else cout<<"orz";
}
|
Kruskal
Kruskal算法的思想:先把边按照权值进行排序，用贪心的思想优先选取权值较小的边，并依次连接，若出现环则跳过此边（用并查集来判断是否存在环）继续搜，直到已经使用的边的数量比总点数少一即可。
这个不需要建图
只需要存边就好了
因为只需要边（）
3步骤解释：（来自题解）
- 快排边长，是为了让每次选的都是所有连接中都能是边长最小的（贪心思想）
- 并查集的作用是：判断有没有连成一个环。若两个点在同一个并查集里面，则说明它们在同一个树里，若连接，就会造成一个环
- 当到了已连边的个数是点的个数-1时，就要停止循环，因为这个时候，最小生成树已经完成了，所有的并查集都连在了一起。
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;
int n,m,i,j,u,v,total;
struct edge
{
int start;
int to;
long long val;
}bian[100000000];
int f[10000000];
long long ans;
int find(int x)
{
if(f[x]==x)
{
return x;
}
else
{
return f[x]=find(f[x]);
}
}
bool cmp(edge a,edge b)
{
return a.val<b.val;
}
void kruskal()
{
for(int i=1;i<=m;i++)
{
u=find(bian[i].start);
v=find(bian[i].to);
if(u==v)
{
continue;
}
ans+=bian[i].val;
f[u]=v;
total++;
if(total==n-1)
{
break;
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
f[i]=i;
}
for(int i=1;i<=m;i++)
{
cin>>bian[i].start>>bian[i].to>>bian[i].val;
}
sort(bian+1,bian+m+1,cmp);
kruskal();
if(total==n-1)
{
cout<<ans;
}
else
{
cout<<"orz";
}
}
|
