代码随想录算法训练营第57天 | 寻宝
寻宝
题目描述
在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。
不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。
给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
输入描述
第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。
接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。
输出描述
输出联通所有岛屿的最小路径总距离
输入示例
7 11 1 2 1 1 3 1 1 5 2 2 6 1 2 4 2 2 3 2 3 4 1 4 5 1 5 6 2 5 7 1 6 7 1
输出示例
6
提示信息
数据范围：
2 <= V <= 10000;
1 <= E <= 100000;
0 <= val <= 10000;如下图，可见将所有的顶点都访问一遍，总距离最低是6.
思路：这是生成最小生成树的经典题目，涉及到了prim算法以及kruskal算法。
1. prim算法
prim算法从结点出发构造最小生成树，适合于稠密图（边多的图）。
主要分为三步：
第一步选择最接近最小生成树的结点；
第二步标记该结点并将其加入最小生成树中；
第三步更新最小生成树的路径大小。
#include<iostream>
#include<vector>
#include<climits>
using namespace std;
int main(){
int v, e;
int v1, v2, val;
cin >> v >> e;
vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));
for(int i = 0; i < e; i ++){
cin >> v1 >> v2 >> val;
grid[v1][v2] = val;
grid[v2][v1] = val;
}
vector<int> minDist(v + 1, 10001);
vector<bool> visited(v + 1, false);
for(int i = 1; i < v; i ++){
int cur = -1;//第一步选择最接近最小生成树的结点
int min = INT_MAX;
for(int j = 1; j <= v; j ++){
if(!visited[j] && minDist[j] < min){
min = minDist[j];
cur = j;
}
}
visited[cur] = true;//第二步开始进行标记
for(int k = 0; k <= v; k ++){//第三步开始更新路径
if(!visited[k] && grid[cur][k] < minDist[k]){
minDist[k] = grid[cur][k];
}
}
}
int result = 0;
for(int i = 2; i <= v; i ++){
result += minDist[i];
}
cout << result << endl;
}2. kruskal算法
kruskal算法是从边出发生成最小生成树，适用于稀疏图（边少的图）。
这里需要首先对边的权值进行排序，所以涉及到将所有边统计下来，然后后面不断加入并查集，判断是否处于同一个集合中。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct edge{
int l, r, val;
};
int v, e;
vector<int> parent(10001, 0);
void init(){
for(int i = 0; i < v; i ++){
parent[i] = i;
}
}
int find(int u){
return u == parent[u] ? u : parent[u] = find(parent[u]);
}
bool isSame(int u, int v){
u = find(u);
v = find(v);
return u == v;
}
void join(int u, int v){
u = find(u);
v = find(v);
if(u == v) return;
parent[v] = u;
}
bool cmp(edge& a, edge& b){
return a.val < b.val;
}
int main(){
while(cin >> v >> e){
init();
vector<edge> grid(e);
int result = 0;//统计所有的权值
for(int i = 0; i < e; i ++){
cin >> grid[i].l >> grid[i].r >> grid[i].val;
}
//对边的权值按照由小到大的顺序排列
sort(grid.begin(), grid.end(), cmp);
for(int i = 0; i < e; i ++){
if(isSame(grid[i].l, grid[i].r)) continue;
result += grid[i].val;
join(grid[i].l, grid[i].r);
}
cout << result << endl;
}
}
感谢你的阅读，希望我的文章能够给你帮助，如果有帮助，麻烦点赞加收藏，或者点点关注，非常感谢。
如果有什么问题欢迎评论区讨论！
原文地址：https://blog.csdn.net/m0_68237332/article/details/142580754
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！