Kruskal模板

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz

输入输出格式

输入格式：

第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）

接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式：

输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz

输入输出样例

输入样例#1： 4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3 输出样例#1： 7

说明

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=20

对于40%的数据：N<=50，M<=2500

对于70%的数据：N<=500，M<=10000

对于100%的数据：N<=5000，M<=200000

样例解释：

所以最小生成树的总边权为2+2+3=7

【题解】

#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int maxn = 5010, maxm = 200010; int r[maxm], u[maxm], v[maxm], w[maxm]; int p[maxn], n, m; void Init() { for (int i = 0; i < n; i++) p[i] = i; for (int i = 0; i < m; i++) r[i] = i; } int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); // p[x]=find(p[x]); } int cmp(const int i, const int j) { return w[i] < w[j]; } int kruskal() { int ans = 0; Init(); sort(r, r + m, cmp); for (int i = 0; i < m; i++) { int e = r[i]; int x = find(u[e]), y = find(v[e]); if (x != y) { ans += w[e]; p[x] = y; } } return ans; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { scanf("%d%d%d", &u[i], &v[i], &w[i]); u[i]--; v[i]--; } printf("%d\n", kruskal()); return 0; }