🟦 Prim-1 🚏《公交站点统一采购》

（完整邻接矩阵，练 $O(n^2)$ Prim 基础模板）

题目背景

在 兔猫信奥学院，加菲老师要在 $n$ 个公交站点之间修建“直连通道”。 任意两个站点之间都可以直接修建，费用由学院调研给出。为了省钱，小兔和小猫希望只修建 恰好 $n-1$ 条通道，让所有站点互相可达，并且总费用最小。

题目描述

给定一个 $n \times n$ 的费用矩阵 $c$（无向图，矩阵对称），其中 $c_{i,i}=0$，$c_{i,j}$ 表示站点 $i$ 与站点 $j$ 之间直连的费用。 请输出把所有站点连通的最小总费用（最小生成树的权值和）。

输入格式

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

输出格式

输出一个整数：最小总费用。

数据范围

• $2 \le n \le 2000$
• $0 \le c_{i,i}=0$
• $1 \le c_{i,j} \le 10^9 \ (i\ne j)$
• 保证矩阵对称且图连通（因为任意两点都有边）

3
0 1 2
1 0 1
2 1 0

2

解释： 选边 $1-2(1)$、$2-3(1)$，总费用 $2$。

4
0 5 5 100
5 0 5 100
5 5 0 100
100 100 100 0

110

解释： 先用三条费用为 $5$ 的边把 $1,2,3$ 连起来（取其中两条），再用一条费用 $100$ 的边连到点 $4$，总费用 $10+100=110$。