Problem 2690 --Graph II - Minimum Spanning Tree

2690: Graph II - Minimum Spanning Tree

上一题 正确率: $50.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $4$ 正确数量 $2$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 STL

Description

Minimum Spanning Tree 

For a given weighted graph G=(V,E), find the minimum spanning tree (MST) of G and print total weight of edges belong to the MST.

Input

In the first line, an integer n denoting the number of vertices in G is given. In the following n lines, a n×n adjacency matrix A which represents G is given. aij denotes the weight of edge connecting vertex i and vertex j. If there is no edge between i and j, aij is given by -1.

Output

Print the total weight of the minimum spanning tree of G.

Sample Input复制

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

Sample Output复制

5

提示

1≤n≤100

0≤aij≤2,0000(if aij≠−1) 

aij=aji 

G is a connected graph

推荐代码 查看2690 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$3 $ms] 海燕 938774 2022-12-31 21:57:46
内存最少[$2124 $KB] 王天驰 808354 2022-02-05 15:29:42
第一AC 王天驰 808354 2022-02-05 15:29:42
第一挑战 hevttccao 660306 2020-11-17 21:42:26

赛题来源/所属竞赛 会津大学《挑战数据结构与算法》 挑战数据结构与算法

竞赛编号 竞赛名称 竞赛时间 访问比赛