简介

最小生成树指在连通图中边权和最小的生成树。

Kruskal

前置知识

并查集

Kruskal 是通过并查集实现，使每一个单独的树作为一个集合，刚开始每个顶点自成一个集合。将原图中所有边按照边权大小排序，每次取出边权最小的一条，若它可以联通两个还未联通的树，则使用这条边，否则舍弃。

int N, M, st[5003] = {0};
struct Edg {
  int X, Y;
  long long Z;
} edg[200003];
auto cmp = [](Edg x, Edg y) -> bool {
  return x.Z < y.Z;
};
std::sort(edg+1, edg+M+1, cmp); // 排序
for(int i = 1; i <= N; ++i) 
  st[i] = i; // 初始化并查集
auto find = [&](auto && find, int x) -> int {
  while(st[x] != x) x = st[x];
  return x;
}; // 并查集模板
long long ans = 0ll;
int cnt = 0;
for(int i = 1; i <= M; ++i) {
  int sx = find(find, edg[i].X), 
      sy = find(find, edg[i].Y);
  if(sx == sy) // 判断是否使用
    continue;
  ans += edg[i].Z;
  st[sx] = sy;
  if(++cnt >= N-1) 
    break; // 优化
}