constint N =510, M =1e5+10, INF =0x3f3f3f3f;int n, m, dist[M], st[M], g[N][N];// g 数组用邻接矩阵存储图intprim(){memset(dist,0x3f,sizeof dist);
dist[1]=0;int res =0;for(int i =0; i < n; i ++){int t =-1;// t 表示不在 S 集合中距离 S 集合距离最短的结点,-1 表示还没找到for(int j =1; j <= n; j ++)if(!st[j]&&(t ==-1|| dist[j]< dist[t]))
t = j;
st[t]=true;if(dist[t]== INF)return INF;// 找到一个点与图是不联通的
res += dist[t];// 这个结点到 S 集合的边权为答案for(int j =1; j <= n; j ++)
dist[j]=min(dist[j], g[t][j]);// 用 t 更新其他点的距离}return res;}
int n, m, p[N];structNode{int a, b, c;}e[M];intfind(int x)// 并查集{
p[x]= p[x]!= x ?find(p[x]): p[x];}intkruskal(){sort(e, e + m,[&](Node &a, Node &b){// 将每条边的权值从小到大排序,这里使用了 Lambdareturn a.c < b.c;});int res =0, cnt =0;for(int i =0; i < m; i ++){int a = e[i].a, b = e[i].b, c = e[i].c;
a =find(a), b =find(b);if(a != b)// 如果 a b 不连通{
p[a]= b;
res += c;
cnt ++;}}if(cnt < n -1)return INT_MAX;return res;}