题目地址：

https://www.acwing.com/problem/content/1142/

农夫约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。约翰的农场的编号是$1$，其他农场的编号是$2\sim n$。为了使花费最少，他希望用于连接所有的农场的光纤总长度尽可能短。你将得到一份各农场之间连接距离的列表，你必须找出能连接所有农场并使所用光纤最短的方案。

输入格式：
第一行包含一个整数$n$，表示农场个数。接下来$n$行，每行包含$n$个整数，输入一个对角线上全是$0$的对称矩阵。其中第$x+1$行$y$列的整数表示连接农场$x$和农场$y$所需要的光纤长度。

输出格式：
输出一个整数，表示所需的最小光纤长度。

数据范围：
$3\le n\le 100$
每两个农场间的距离均是非负整数且不超过$100000$。

其实就是求最小生成树的总边长。可以用Prim算法。其思路大致是维护一个集合，同时维护所有不在这个集合里的点与该集合的最短距离，然后依次将距离最小的点加入集合，直到所有点都加进去为止。具体是这样的：
1、任选一个点$x$，开一个距离数组$d$，令$d[x]=0$，其余点的$d$定为$+\infty$。
2、进行$n$次循环，$n$是图的点数，每次循环的时候，找到不在$S$中并且$d$最小的点，将其加入集合$S$（第一次循环的时候$S=\varnothing$，由于选中了$x$令$d[x]=0$，所以$x$是第一个加入$S$的点），并累加该边的长度；
3、循环结束后，就将$n$个点都加入了$S$，也就得到了一棵最小生成树。

关于算法的正确性，只需注意每次加的边一定能包含在某个最小生成树里即可。在已经加入的点的集合是$S$时，如果某个从$x$出发的到达$y$的边在Prim算法里没有被选入，那么在生成的最小生成树里，由于$x$与$y$是连通的，所以这棵树加上$x\to y$这条边之后，就形成了一个环。这个环与$S$相交的点除了$x$之外，一定还有另一个点$z$，从$z$出发向外的一条边被这个最小生成树选中了，而将这条边换成$x\to y$这条边，能得到一个不会更差的最小生成树（这是由Prim算法选边的方式决定的）。这就证明了$x\to y$这条边是可以作为某个最小生成树的边的。再由数学归纳法即得Prim算法的正确性。

代码如下：

#include <iostream>
#include <cstring>
using namespace std;const int N = 110;
int n;
int a[N][N];
// dist[i]存i与集合的最短距离
int dist[N];
// st[i]存i这个点是否已经被选入集合
bool st[N];int prim() {memset(dist, 0x3f, sizeof dist);int res = 0;// 选中1号点，从这个点开始扩张为最小生成树dist[1] = 0;// 循环n次，每次加入一个点for (int i = 0; i < n; i++) {// 找到还没选中的点里与集合最小距离最小的点int t = -1;for (int j = 1; j <= n; j++)if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;// 累加边权，并将t并入集合res += dist[t];st[t] = true;// 以t的邻边来更新未加入集合的点的最小距离for (int j = 1; j <= n; j++)if (!st[j] && dist[j] > a[t][j])dist[j] = a[t][j];}return res;
}int main() {cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> a[i][j];cout << prim() << endl;return 0;
}

时间复杂度$O(n^2)$，空间$O(n)$。