4949. 最小生成树
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 对于给定的带权图 $ G=(V, E) $，找到其最小生成树$（MST）$，并输出属于该最小生成树的所有边的权重总和。 ## 输入格式 第一行给出一个整数 $ n $，表示图 $ G $ 中的顶点数量。接下来的 $ n $ 行构成一个 $n \times n $ 的邻接矩阵 $A $，其中$ a_{ij} $表示顶点 $ i $和顶点$ j $ 之间的边的权重。若两顶点之间没有边，则 $a_{ij} $的值为 $-1$。 ## 输出格式 输出图 $ G $ 的最小生成树的边权重总和。 ## 输出格式 - $1 \leq n \leq 100 $ - 若 $a_{ij} \neq -1$，则 $0 \leq a_{ij} \leq 2000 $ - $a_{ij} = a_{ji} $（图为无向图） - 图 $ G $ 是连通图 ## 输入 ```in1 5 -1 2 3 1 -1 2 -1 -1 4 -1 3 -1 -1 1 1 1 4 1 -1 3 -1 -1 1 3 -1 ``` ## 输出 ```out1 5 ``` ## 参考资料 《算法导论》，托马斯·H·科门、查尔斯·E·莱瑟森、罗纳德·L·里夫斯、克利福德·斯坦因 著，麻省理工学院出版社。