湛江免费建站公司,电商网站seo,上海工商局官网查询,大学学校网站建设方案训练营六十二天打卡#xff0c;图论比较难#xff0c;坚持下来胜利就在眼前#xff01; 53.卡码网【寻宝】
题目链接
解题过程
没做过类似的题目#xff0c;跟着答案敲了一遍最小生成树 可以使用 prim算法 也可以使用 kruskal算法计算出来。prim算法 是从节点的角度 采用…训练营六十二天打卡图论比较难坚持下来胜利就在眼前 53.卡码网【寻宝】
题目链接
解题过程
没做过类似的题目跟着答案敲了一遍最小生成树 可以使用 prim算法 也可以使用 kruskal算法计算出来。prim算法 是从节点的角度 采用贪心的策略 每次寻找距离 最小生成树最近的节点 并加入到最小生成树中。prim算法核心就是三步prim三部曲 第一步选距离生成树最近节点第二步最近节点加入生成树第三步更新非生成树节点到生成树的距离即更新minDist数组 minDist数组 用来记录 每一个节点距离最小生成树的最近距离。
prim算法
#includeiostream
#includevector
#includeclimits
using namespace std;int main() {int v, e;cin v e;vectorvectorintgrid(v 1, vectorint(v 1, 10001));while (e--) {int x, y, val;cin x y val;grid[x][y] grid[y][x] val;}vectorintminDist(v 1, 10001);vectorboolisInTree(v 1, false);for (int i 1; i v; i) { // v - 1条边int cur -1;int minVal INT_MAX;for (int j 1; j v; j) {if (!isInTree[j] minDist[j] minVal) {minVal minDist[j];cur j;}}isInTree[cur] true;for (int j 1; j v; j) {if (!isInTree[j] grid[cur][j] minDist[j]) {minDist[j] grid[cur][j];}}}int result 0;for (int i 2; i v; i) {result minDist[i];}cout result endl;return 0;
}prim 算法是维护节点的集合而 Kruskal 是维护边的集合。kruscal的思路 边的权值排序因为要优先选最小的边加入到生成树里遍历排序后的边 如果边首尾的两个节点在同一个集合说明如果连上这条边图中会出现环如果边首尾的两个节点不在同一个集合加入到最小生成树并把两个节点加入同一个集合 将两个节点加入同一个集合又如何判断两个节点是否在同一个集合呢 答案是并查集并查集主要就两个功能 将两个元素添加到一个集合中判断两个元素在不在同一个集合
Kruskal算法
#includeiostream
#includevector
#includealgorithm
using namespace std;
struct Edge{int l, r, val;
}; // l r 为边val为边的数值
vectorintfather;
void init(int v) {father.resize(v 1);for (int i 0; i v; i) {father[i] i;}
}
int find(int u) {return u father[u] ? u : father[u] find(father[u]);
}void join(int u, int v) {u find(u);v find(v);if (u ! v) {father[v] u;}
}int main() {int v, e;cin v e;init(v);vectorEdgeedges;while (e--) {int l, r, val;cin l r val;Edge edge;edge.l l;edge.r r;edge.val val;edges.push_back(edge);}sort(edges.begin(), edges.end(), [](Edge e1, Edge e2)-bool{return e1.val e2.val;});int result 0;for (Edge edge : edges) {int x find(edge.l);int y find(edge.r);if (x ! y) {result edge.val;join(x, y);}}cout result endl;return 0;
}
