具体做法： 首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
把所有边按权值从小到大排序
遍历每条边 如果这条边的两个顶点一个在树内一个在树外 则将顶点入树
保证了每条边的权值都是最小的
最终得到的树即为最小生成树
并查集的作用是判断两个顶点是否在一个集合（在一个树内）并且合并两个顶点到一棵树
假设排序后第一条边为从顶点i到顶点j权值为v的边，显然这条边是连通图中最短的边，那么可知这条边也是从i到j最短的边
#include<bits/stdc++.h> #define INF 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false) #define endl '\n' using namespace std; typedef long long ll; const int maxn = 1e6 + 10; int n, m; int f[maxn]; struct Egde { int from, to, val; }edge[maxn];//结构体存边 void init() { for (int i = 1;i <= n;++i)f[i] = i; } int get_father(int x) { return x == f[x] ? x : f[x] = get_father(f[x]); } void unite(int a, int b) { f[get_father(a)] = get_father(b); } bool cmp(Egde a ,Egde b) { return a.val < b.val; } int main() { cin >> n >> m; init(); ll ans = 0; for (int i = 1;i <= m;++i) { scanf("%d %d %d", &edge[i].from, &edge[i].to, &edge[i].val); } sort(edge + 1, edge + m + 1, cmp);按权值从小到大排序 for (int i = 1;i <= m;++i) { if (get_father(edge[i].from) != get_father(edge[i].to)) {//如果两个顶点不在同一个集合，则合并 ans += edge[i].val; unite(edge[i].from, edge[i].to); } } printf("%d\n", ans); return 0; }
