[模板问题] 最小生成树 (Kruskal / Prim)
最编程
2024-03-21 13:43:19
...
【模板】最小生成树
题目描述
如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz
。
输入格式
第一行包含两个整数 N , M N,M N,M,表示该图共有 N N N 个结点和 M M M 条无向边。
接下来 M M M 行每行包含三个整数 X i , Y i , Z i X_i,Y_i,Z_i Xi,Yi,Zi,表示有一条长度为 Z i Z_i Zi 的无向边连接结点 X i , Y i X_i,Y_i Xi,Yi。
输出格式
如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz
。
样例 #1
样例输入 #1
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
样例输出 #1
7
提示
数据规模:
对于 20 % 20\% 20% 的数据, N ≤ 5 N\le 5 N≤5, M ≤ 20 M\le 20 M≤20。
对于 40 % 40\% 40% 的数据, N ≤ 50 N\le 50 N≤50, M ≤ 2500 M\le 2500 M≤2500。
对于 70 % 70\% 70% 的数据, N ≤ 500 N\le 500 N≤500, M ≤ 1 0 4 M\le 10^4
上一篇: vue 生物报告