最小生成树
prim：点
kruskal：边
都是贪心
prim算法精讲
从顶点的角度，按照贪心算法，一个一个加入生成树。
关键点：
minDist表示不是生成树上的点到生成树的最小距离。
inTheTree表示是否是生成树上的点
步骤：
1.选取距离最小的点加入生成树
2.更新minDist
#include <iostream>
#include <vector>
#include <climits>
using namespace std;int main() {//inputint v, e, v1, v2, val;cin >> v >> e;vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));while (e--) {cin >> v1 >> v2 >> val;grid[v1][v2] = val;grid[v2][v1] = val;}vector<int> minDist(v + 1, 10001);vector<bool> inTheTree(v + 1, false);for (int i = 1; i <= v; i++) {// cout << "i=" << i << endl;//选一个距离最近的点加入生成树//条件1：不在生成树里//条件2：距离最近int cur = -1;//随便选一个不存在的数int minVal = INT_MAX;//选一个最大的数for (int j = 1; j <= v; j++) {if (!inTheTree[j] && minDist[j] < minVal) {cur = j;minVal = minDist[j];}}inTheTree[cur] = true;//更新minDist，其他非生成树的点距离生成树的距离for (int j = 1; j <= v; j++) {if (!inTheTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}// for (int c = 1; c <= v; c++) {// cout << minDist[c] << " ";// }}int result=0;for (int i = 2; i <= v; i++) {result += minDist[i];}// for (int i = 0; i <= v; i++) {// cout << minDist[i] << " ";// }cout << result << endl;return 0;
}kruskal算法精讲
对所有边从小到大排序，如果这条边的两头不在同一个集合里，result加入这条边，集合中也加入这两个点。
//kruskal
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int N=10001;
vector<int> father(N,-1);struct Edge{int l,r,val;
};void init(){for(int i=0;i<N;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){return;}father[v]=u;
}int main() {int v, e, v1, v2, val;cin >> v >> e;// v = 10;// e = 11;// vector<vector<int>> graph;// graph = {// {1,2,15},// {2,7,65},// {2,3,88},// {4,5,48},// {5,7,45},// {6,7,78},// {6,9,40},// {7,8,22},// {8,9,38},// {8,10,35},// {9,10,52}// };vector<Edge> edges;// int d = 0;while (e--) {cin >> v1 >> v2 >> val;// int v1 = graph[e][0];// int v2 = graph[e][1];// int val = graph[e][2];edges.push_back({v1,v2,val});// d++;}sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {return a.val < b.val;});int result = 0;init();for(Edge edge:edges){int l = find(edge.l);int r = find(edge.r);if(l!=r){result += edge.val;join(l,r);}}cout << result << endl;return 0;
}
