同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1336_最小生成树(MST)之Kruska

2022-5-16 18:17| 发布者: Hocassian| 查看: 32| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-89503784333099-Problem List-采集的数据-后羿采集器.html

Pro.ID

1336

Title

最小生成树(MST)之Kruskal

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1336

AC

319

Submit

1183

Ratio

26.97%

时间&空间限制

Time Limit: 400/200 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

描述

给出一个无向网，求该无向网的最小生成树。各条边的权重不超过100000。

本题与上一题的测试数据是一样的，本题请用Kruskal算法来做，以便与上一题做比较。

输入

输入的第一行是一个整数N，表示该网的顶点个数。 3 ≤ N ≤ 100

接下来是N行，每行N个整数，表示每个顶点到其余顶点的距离。

输出

Description

给出一个无向网，求该无向网的最小生成树。各条边的权重不超过100000。

本题与上一题的测试数据是一样的，本题请用Kruskal算法来做，以便与上一题做比较。

Input

输入的第一行是一个整数N，表示该网的顶点个数。 3 ≤ N ≤ 100

接下来是N行，每行N个整数，表示每个顶点到其余顶点的距离。

Output

输出该最小生成树的权重。

Sample Input

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

Sample Output

Author

John

样例输入