🟦 Prim-2 🛠️《损坏线路的最省修复》

（矩阵里 0 表示无边，可能不连通，必须输出 -1）

题目背景

兔猫信奥学院的线路年久失修，很多站点之间已经没有可用线路。 加菲老师给出修复费用表：若两点之间没有线路，则记为 0（不可用）。 小兔和小猫要判断能否修成一个连通网络；若能，求最小修复总费用。

题目描述

给定 $n \times n$ 矩阵 $c$：

• $c_{i,i}=0$
• 对于 $i\ne j$：若 $c_{i,j}=0$ 表示 没有边；若 $c_{i,j}>0$ 表示修复费用

求：若能连通所有点，输出最小生成树总费用；否则输出 -1。

输入格式

第一行整数 $n$。 接下来 $n$ 行，每行 $n$ 个整数表示矩阵 $c$。

输出格式

输出最小总费用；若无法连通输出 -1。

数据范围

• $2 \le n \le 2500$
• $0 \le c_{i,j} \le 10^9$
• 矩阵对称（无向）

样例 1

4
0 2 0 6
2 0 3 0
0 3 0 1
6 0 1 0

6

解释： 可用边有 $1-2(2)$、$2-3(3)$、$3-4(1)$、$1-4(6)$。 MST 选 $1-2(2)$、$2-3(3)$、$3-4(1)$，总费用 $6$。

样例 2

3
0 5 0
5 0 0
0 0 0

-1

解释： 点 3 与其他点没有任何可用线路，无法连通。