洛谷 P3366 【模板】最小生成树
题目
给出一个无向图,求出最小生成树,如果该图不连通,则输出orz
题目链接【模板】最小生成树 - 洛谷
输入
第一行包含两个整数N、M,表示该图共有N个结点和M条无向边。(N<=5000,M<=200000)接下来M行每行包含三个整数Xi、Yi、Zi,表示有一条长度为Zi的无向边连接结点Xi、Yi
输出
输出包含一个数,即最小生成树的各边的长度之和;如果该图不连通则输出orz
样例
输入1
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出1
7
题解
本题为最小生成树的模版题,对于构造最小生成树,最经典的两个算法是Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法。两者都利用了最小生成树的MST性质。MST性质,简单来说,假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中u属于U,v属于(V-U),则必存在一棵包含边(u,v)的最小生成树。
此性质可以用反证法证得,不是本文重点,感兴趣可以出门百度。
MST性质其实可以看作是一种贪心的思想(每一步选取当前的最优解)
具体的解释在两种算法的代码中,其中Prim的代码(可能)并不能过这道题。
(在macOS中数组不被允许开到5000*5000… 所以不能用邻接矩阵来存储边,可能能用邻接链表来存)
Prim算法代码
Prim算法:先随意确定一个顶点,之后在未选择的边集合中选择一条连接这个顶点的最短的一条边,将这个边连的顶点加入到已选择的点的集合,同时这条边也设置为已选择。重复这个过程,直至所有点都被选择。时间复杂度O(n^2)。(n为顶点的数量 )
算法的关键在于设置一个辅助数组closedge,closedge[I]表示从顶点i出发,到达已选择的节点和边生成的树的最小的距离。
#include <stdio.h>
#define MAX 999999999
struct{
Int lowcost; //U集合代表已经选择的顶点的集合,V表示全体顶点集合
}closedge[5005]; //Prim算法的辅助数组,用于存储从U到V-U具有最小代价的边
int main(){
Int arc[10][10]; //邻接矩阵,存储边的信息
int n, m, k, len;
len = 0;
scanf(“%d %d”, &n, &m);
for (int I = 1; I <= n; I++) //初始化邻阶矩阵
for (int j = 1; j <= n;j++){
arc[I][j] = MAX; //初始点与点直接都不连通,距离设为一个极大值
if (I == j)
arc[I][j] = 0; //自己到自己的距离设为0
}
for (int i = 0; i < m; i++){
int x,y,z;
scanf(“%d %d %d”, &x, &y, &z); //读入边
arc[x][y] = z;
arc[y][x] = z;
}
K = 1; //选出第一个加入U的顶点 (集合U存已经被选择的顶点)
for (int i = 1; i <= n;i++){
if (i != k)
closedge[i].lowcost = arc[i][k];
}
For (int I = 2; I <= n;i++){ //还有n-1个顶点需要加入集合U
int min = MAX;
int flag;
flag = k;
for (int j = 1; j <= n; j++){
if ((closedge[j].lowcost > 0) && (min > closedge[j].lowcost)){
min = closedge[j].lowcost; //找到当前辅助数组中距离最小的边
flag = j;
}
}
K = flag; //将最小的边和对应的顶点加入集合
len = len + closedge[k].lowcost; //统计最小生成树的长度
closedge[k].lowcost = 0; //以赋值为0表示顶点k已经被选择过
for (int j = 1; j <= n; j++){
if (arc[k][j] < closedge[j].lowcost){
closedge[j].lowcost = arc[k][j]; //更新closedge数组(因为有新的点和边加入了当前的树)
}
}
}
for (int i = 1; i <= n; i++)
If (closedge[I].lowcost != 0){ //如果还有点未被加入集合U,表示这个图不连通
printf("orz");
return 0;
}
printf("%d", len);
return 0;
}
Kruskal算法代码
Kruskal算法:假设连通网N=(V,{E}),则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。依次类推,直至T中所有顶点都在同一连通分量上为止。时间复杂度为O(eloge)(e为网中边的数目)
简单地来说,就是用一个结构体数组存边(结构体中包含两个顶点和边的长度),然后将这个数组生序排序,之后从头到尾扫一遍,利用并查集的方法去选择边。
这里再解释一下并查集的应用,当边按边长从小到大排好后,我们要做的就是从依次从中选择一条边,而这条边的两个顶点不能都已经在生成树中(否则就形成了一个环,这不符合最小生成树的定义),于是我们利用并查集判断环的功能,来进行筛选,如果成环,则跳过,查看下一条边,否则加入生成树中。
(下面这个代码没有判断此图是否连通,因为忘写了,结果也能过评测…要判断的话,我觉得可以在最后遍历一遍顶点,如果存在大于一个顶点它的父亲节点是它自己,就说明此图不连通)
并查集的内容可以参考以下两篇文章
朋友圈(并查集)
洛谷 P3367 【模板】并查集
#include <stdio.h>
struct edge{
Int x,y,v; //x,y存储边的两个端点 v存储边的长度
};
struct edge edges[200005];
int n,m,ans;
Int f[5005]; //并查集操作中存储节点i的父亲节点f[i]
void quicksort(int l, int r){ //快速排序,将存边的数组按边值升序排序,具体可以百度,C++可以直接用sort函数(自己再写一个比较函数即可)
int i,j,m,temp;
I = l;
j = r;
m = edges[(l+r) / 2].v;
while (I <= j){
while (edges[I].v < m)
I++;
while (edges[j].v > m)
j—;
if (I <= j){
temp = edges[I].x;
edges[I].x = edges[j].x;
edges[j].x = temp;
temp = edges[I].y;
edges[I].y = edges[j].y;
edges[j].y = temp;
temp = edges[I].v;
edges[I].v = edges[j].v;
edges[j].v = temp;
I++;
j—;
}
}
if (l < j)
quicksort(l, j);
if (I < r)
quicksort(I, r);
}
int search(int x){ //并查集中的寻找根节点的操作
if (f[x] == x)
return x;
else
return f[x] = search(f[x]); //一种路径压缩的手段
}
int main(){
ans = 0;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++){
scanf("%d %d %d", &edges[i].x, &edges[i].y, &edges[i].v); //读入边集
}
quicksort(0, m-1); //对边进行排序
for (int i = 1; i <= n; i++)
f[i] = i; //对父亲节点数组进行初始化
for (int i = 0; i < m; i++){
if (search(edges[i].x) == search(edges[i].y))
continue; //如果该边的两个节点已经在生成树中,则舍去这条边
f[search(edges[i].x)] = search(edges[i].y); //否则将这条边加入生成树(运用并查集的合并集合操作)
ans = ans + edges[i].v; //记录最小生成树的长度
}
printf("%d", ans);
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)