题目描述
想象一下你是个城市基建规划者，地图上有 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]
题解
这题乍一看，就知道是最小生成树问题了，正好，借此机会，复习一把最小生成树。
解法1：kruskal算法
kruskal算法核心思想：
1）初始阶段，每个点互不相识，各自为一个孤岛。
2）以题设给定的“边”为入手，不断的通过整合边所连接两个点，让所有孤岛都连接到一起。
3）利用贪心算法，选择cost小的边为起点，遍历所有的边。
4）遍历的过程中，如果发现当前边所在的两个点在两个孤岛上，则将他们合并。这一步采用的并查集方法（即为不同的集合寻找father，father相同的节点，为同一个集合）。
思想还是比较清晰和简洁，我没有去证明为什么第三步用贪心算法一定是可以的。。有兴趣的可以查阅资料再证明一下。
代码
class Solution {
public:
int find(int x) //不断向上找，直到找到下标和元素相同的点；不理解背后原因的，可以学习下树的数组表示发。
{
while(x != p[x]) x = p[x];
return x;
}
int minimumCost(int N, vector<vector<int>>& connections) {
int ans = 0;
int point_num = 0;
//sort重定义比较是重载的<号，为真则不交换，否则交换。
//基于上述原则，对cmp返回对应的true or false
auto cmp = [](vector<int> &a, vector<int> &b){return a[2] < b[2];};
for(int i = 0; i <= N; i++) {
p.push_back(i);
}
sort(connections.begin(), connections.end(), cmp);//按cost值排序，采用贪心算法
for (auto conn : connections) {
int px = find(conn[0]),py = find(conn[1]);
if(px != py) { //如果该边所在的两个节点不在同一个集合
p[px] = py; //合并集合
ans += conn[2];
point_num++;
//对于无向图的话，至少需要n-1条边可以使得图是联通的；
//如果对于有向图的话，至少需要n条边才可以使得图是联通的
if(point_num == N - 1){
return ans;
}
}
}
return -1;
}
private:
vector<int> p; //集合关系表，用一个数组来描述N个节点的集合关系；等同于树的数组表示方法。
};
kruskal就是贪心加并查集，，而且写起来也比较简单，非常的模板化。
解法2：prim算法
prim算法核心思想
1）以某一个点为起点（通常为数组的第一个点）。以“点”为参照物，从该点所在“集合”的边当中依次选择cost最小的边去连接一个“新的”节点。
2）在一个结合新（要注意是新的，否则会死循环）加入一个节点后，将会扩大原有的集合，而该集合所连接的边和点都会发生变化。针对这类问题，选择小顶堆作为数据结构。
3）当该集合中有N个点时，所有的点都已经被访问过了。
代码
class Solution {
public:
int minimumCost(int N, vector<vector<int>>& connections) {
//重载priority_queue的比较函数，priority_queue默认是大顶堆，重载的是<号
//默认情况下如果左边参数大于右边参数，则说明左边形参的优先级低于右边形参，会将左边的放到后面
//构建小顶堆时，我们实现一个>号的判断即可，大于返回true，优先级低，被放到后面，则小的会放前面
struct cmp {
bool operator () (const vector<int> &a, const vector<int> &b) {
return a[2] > b[2];
}
};
int selected = 0, ans = 0;
//构建点和cost的集合关系，本质是个三维数组，第一维是起点，二维是<终点、开销>
vector<vector<pair<int,int>>> edgs(N+1,vector<pair<int,int>>());
//构建小顶堆，将最合适的点放在最前面
priority_queue<vector<int>,vector<vector<int>>,cmp> pq;
vector<int> visit(N+1, 0);
//初始化边集合
for(auto re : connections){
edgs[re[0]].push_back(make_pair(re[1],re[2]));
edgs[re[1]].push_back(make_pair(re[0],re[2]));
}
//本次选择1为起点，如果1点没有变，则1永远是孤岛。本次选择1为起点
if(edgs[1].size() == 0){
return -1;
}
selected = 1;
visit[1] = true;
//起点1所在的边放入小顶堆
for(int i = 0;i < edgs[1].size(); ++i){
pq.push(vector<int>({1,edgs[1][i].first,edgs[1][i].second}));
}
//遍历小顶堆
while(!pq.empty()) {
auto curr = pq.top();pq.pop();
if(!visit[curr[1]]){
visit[curr[1]] = true;
ans += curr[2];
//依次取出cost最小的边所在的点加入集合
for(auto e : edgs[curr[1]]){
pq.push(vector<int>({curr[1],e.first,e.second}));
}
selected++;
if(selected == N){ //如果N个节点都在时，则结束循环
return ans;
}
}
}
return -1;
}
};
