题目来源:53. 寻宝(第七期模拟笔试)
prim三部曲
- 第一步,选距离生成树最近节点
- 第二步,最近节点加入生成树
- 第三步,更新非生成树节点到生成树的距离(即更新minDist数组 用来记录 每一个节点距离最小生成树的最近距离,即记录了 所有非生成树节点距离生成树的最小距离)
#include<iostream>
#include<vector>
#include <climits>using namespace std;
int main() {int v, e;int x, y, k;cin >> v >> e;// 填一个默认最大值,题目描述val最大为10000vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));while (e--) {cin >> x >> y >> k;// 因为是双向图,所以两个方向都要填上grid[x][y] = k;grid[y][x] = k;}// 所有节点到最小生成树的最小距离vector<int> minDist(v + 1, 10001);// 这个节点是否在树里vector<bool> isInTree(v + 1, false);// 我们只需要循环 n-1次,建立 n - 1条边,就可以把n个节点的图连在一起for (int i = 1; i < v; i++) {// 1、prim三部曲,第一步:选距离生成树最近节点// 初始化 要在每次寻找加入最小生成树节点前int cur = -1; // 选中哪个节点 加入最小生成树int minVal = INT_MAX;for (int j = 1; j <= v; j++) { // 1 - v,顶点编号,这里下标从1开始// 选取最小生成树节点的条件:// (1)不在最小生成树里// (2)距离最小生成树最近的节点if (!isInTree[j] && minDist[j] < minVal) {minVal = minDist[j];cur = j;}}// 2、prim三部曲,第二步:最近节点(cur)加入生成树isInTree[cur] = true;// 3、prim三部曲,第三步:更新非生成树节点到生成树的距离(即更新minDist数组)// cur节点加入之后, 最小生成树加入了新的节点,那么所有节点到 最小生成树的距离(即minDist数组)需要更新一下// 由于cur节点是新加入到最小生成树,那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢for (int j = 1; j <= v; j++) {// 更新的条件:// (1)节点是 非生成树里的节点// (2)与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小// 很多录友看到自己 就想不明白什么意思,其实就是 cur 是新加入 最小生成树的节点,那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入,需要更新一下数据了if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}}// 统计结果int result = 0;for (int i = 2; i <= v; i++) { // 不计第一个顶点,因为统计的是边的权值,v个节点有 v-1条边result += minDist[i];}cout << result << endl;}