ftp里找到的index文件查看网站建设中,家具定制东莞网站建设,wordpress新建页面没有模板,公司装修怎么做账文章目录1. 题目2. 解题1. Kruskal2. prim1. 题目
想象一下你是个城市基建规划者#xff0c;地图上有 N 座城市#xff0c;它们按以 1 到 N 的次序编号。
给你一些可连接的选项 conections#xff0c;其中每个选项 conections[i] [city1, city2, cost] 表示将城市 city1 …
文章目录1. 题目2. 解题1. Kruskal2. prim1. 题目
想象一下你是个城市基建规划者地图上有 N 座城市它们按以 1 到 N 的次序编号。
给你一些可连接的选项 conections其中每个选项 conections[i] [city1, city2, cost] 表示将城市 city1 和城市 city2 连接所要的成本。连接是双向的也就是说城市 city1 和城市 city2 相连也同样意味着城市 city2 和城市 city1 相连。
返回使得每对城市间都存在将它们连接在一起的连通路径可能长度为 1 的最小成本。 该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项任务则请你返回 -1。
示例 1
输入N 3, conections [[1,2,5],[1,3,6],[2,3,1]]
输出6
解释
选出任意 2 条边都可以连接所有城市我们从中选取成本最小的 2 条。示例 2
输入N 4, conections [[1,2,3],[3,4,4]]
输出-1
解释
即使连通所有的边也无法连接所有城市。提示
1 N 10000
1 conections.length 10000
1 conections[i][0], conections[i][1] N
0 conections[i][2] 10^5
conections[i][0] ! conections[i][1]来源力扣LeetCode 链接https://leetcode-cn.com/problems/connecting-cities-with-minimum-cost 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
图Graph–最小生成树
1. Kruskal
将边的权值排序小的先遍历用并查集检查两个顶点是否合并了没有合并则将该边加入生成树也可以使用优先队列实现相当于排序
class dsu
{vectorint f;
public:dsu(int n){f.resize(n);for(int i 0; i n; i)f[i] i;}void merge(int a, int b){int fa find(a);int fb find(b);f[fa] fb;}int find(int a){int origin a;while(a ! f[a]){a f[a];}return f[origin] f[a];}
};class Solution {
public:int minimumCost(int N, vectorvectorint connections) {dsu u(N1);sort(connections.begin(), connections.end(),[](auto a, auto b){return a[2] b[2];//距离短的边优先});int edge 0, p1, p2, dis, total 0;for(int i 0; i connections.size(); i){p1 connections[i][0];p2 connections[i][1];dis connections[i][2];if(u.find(p1) ! u.find(p2))//两个还未链接{u.merge(p1,p2);edge;total dis;}if(edge N-1)break;}return edgeN-1 ? total : -1;}
};1504 ms 158.6 MB
2. prim
把一个初始顶点的所有边加入优先队列取出最短的边把这条边的另一个顶点相关的边加入队列再取出最小的边重复下去直到所有顶点加入过了
struct cmp
{bool operator()(const pairint,int a, const pairint,int b) const{return a.second b.second;//小顶堆, 距离小的优先}
};
class Solution {
public:int minimumCost(int N, vectorvectorint connections) {vectorbool vis(N1, false);vectorvectorpairint,int edges(N1,vectorpairint,int());for(auto c : connections){edges[c[0]].push_back({c[1],c[2]});edges[c[1]].push_back({c[0],c[2]});}priority_queuepairint,int, vectorpairint,int, cmp q;int to, distance, total 0, edge 0;vis[1] true;for(auto e : edges[1])q.push(e); while(!q.empty()){to q.top().first;distance q.top().second;q.pop();if(!vis[to]){vis[to] true;total distance;edge;if(edge N-1)return total;for(auto e : edges[to])q.push(e); }}return -1;}
};492 ms 40.9 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
