题目地址：https://leetcode-cn.com/problems/connecting-cities-with-minimum-cost/
题目描述
There are N cities numbered from 1 to N.
Youare given connections, where each connections[i] = [city1, city2, cost] represents the cost to connect city1 and city2 together. (A connection is bidirectional: connecting city1 and city2 is the same as connecting city2 and city1.)
Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together. The cost is the sum of the connection costs used. If the task is impossible, return -1.
Example 1:
Input: N = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation:
Choosing any 2 edges will connect all cities so we choose the minimum 2.
Example 2:
Input: N = 4, connections = [[1,2,3],[3,4,4]]
Output: -1
Explanation:
There is no way to connect all cities even if all edges are used.
Note:
1、 1<=N<=10000；
2、 1<=connections.length<=10000；
3、 1<=connections[i][0],connections[i][3]<=N；
4、 0<=connections[i][2]<=10^5；
5、 connections[i][0]!=connections[i][4]；
题目大意
想象一下你是个城市基建规划者，地图上有 N 座城市，它们按以 1 到 N 的次序编号。 给你一些可连接的选项 conections，其中每个选项 conections[i] = [city1, city2, cost] 表示将城市 city1 和城市 city2 连接所要的成本。（连接是双向的，也就是说城市 city1 和城市 city2 相连也同样意味着城市 city2 和城市 city1 相连）。 返回使得每对城市间都存在将它们连接在一起的连通路径（可能长度为 1 的）最小成本。该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项任务，则请你返回 -1。
解题方法
Kruskal算法
本题是标准的最小生成树问题，有Prim和Kruskal算法两个解法。
MST（Minimum Spanning Tree，最小生成树）问题有两种通用的解法，Prim算法就是其中之一，它是从点的方面考虑构建一颗MST，大致思想是：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗MST。因为有N个顶点，所以该MST就有N-1条边，每一次向集合V中加入一个点，就意味着找到一条MST的边。
Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。至于怎么合并到一个集合，那么这里我们就可以用到一个工具——-并查集。换而言之，Kruskal算法就是基于并查集的贪心算法。
具体做法如上所言，不再赘述。
C++代码如下：
class Solution {
public:
int minimumCost(int N, vector<vector<int>>& connections) {
part = N;
parent = vector<int>(N, 0);
for (int i = 0; i < N; ++i)
parent[i] = i;
sort(connections.begin(), connections.end(),
[](const vector<int>& a, const vector<int>& b) { return a[2] < b[2];});
int res = 0;
for (vector<int>& conn : connections) {
int a = conn[0] - 1;
int b = conn[1] - 1;
int cost = conn[2];
int pa = find(a);
int pb = find(b);
if (pa != pb) {
uni(a, b);
res += cost;
}
if (part == 1)
return res;
}
return -1;
}
int find(int a) {
if (parent[a] == a)
return a;
return find(parent[a]);
}
void uni(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa == pb)
return;
parent[pa] = pb;
part --;
}
private:
vector<int> parent;
int part = 0;
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
参考资料： https://www.cnblogs.com/fzl194/p/8722989.html https://www.cnblogs.com/fzl194/p/8723325.html
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发