*最小生成树：
通过的点和边构成的子图，从图的任何一个顶点出发，都可以访问图中所有顶点且代价最小
预备知识：
- 重载运算符
- 并查集
步骤：
1> 按边的权值从小到大排序
2> 按顺序，每次加边，两点已连通则不加
3> 直到有n-1条边
#include <iostream> #include <algorithm> using namespace std; struct Edge { //图的边 int s, t; //起始位置 int w; //权值 bool operator <(const Edge b) const { //C++重载运算符 return w < b.w; } }; Edge b[50001]; //不需邻接矩阵 用 struct存边 int n, m; int father[50001]; int find_f(int x) { if(father[x] == x) return x; father[x] = find_f(father[x]); return father[x]; } int unite(int x, int y) { int a = find_f(x); int b = find_f(y); if(a == b) return 0; father[b] = a; return 1; } int Kruskal() { int x, y; int num = 0, min_w = 0; //记录边 和 最小生成树的费用 for(int i=1; i<=n; i++) father[i] = i;//初始化并查集 sort(b+1, b+m+1); //已定义'<'运算可以直接用sort for(int i=1; i<=m; i++) { x = b[i].s; y = b[i].t; if(!unite(x, y)) continue; //两点已经连通 num ++; //边数增加 min_w += b[i].w; //费用增加 if(num == n-1) break; } return min_w; } void build_graph() { //建图 int x, y, w; cin >> n >> m; for(int i=1; i<=m; i++) { cin >> x >> y >> w; b[i].s = x; b[i].t = y; b[i].w = w; } } int main() { build_graph(); cout << Kruskal() << endl; return 0; }
