题解：最短网络（最小生成树问题）

题目传送门

一、题目描述

农夫约翰需要将所有农场用光纤连接起来，形成一个网络。给定各农场之间的连接距离矩阵，要求找出连接所有农场并使光纤总长度最短的方案。

二、题目分析

这是一个典型的最小生成树（MST）问题。我们需要在给定的带权无向图中，找出一棵包含所有顶点的生成树，并且使得树上所有边的权值之和最小。

三、解题思路

使用Prim算法来解决最小生成树问题：
1. 从任意一个顶点开始（这里选择1号农场）
2. 每次选择距离当前生成树最近的顶点加入树中
3. 更新其他顶点到生成树的距离
4. 重复直到所有顶点都加入生成树

四、算法讲解（Prim算法）

以样例输入为例：

4
0  4  9  21
4  0  8  17
9  8  0  16
21 17 16  0

算法执行过程：
1. 初始选择1号农场，距离集合{1}最近的农场是2号（距离4）
2. 加入2号后，距离集合{1,2}最近的农场是3号（距离8）
3. 加入3号后，距离集合{1,2,3}最近的农场是4号（距离16）
4. 总长度=4+8+16=28

五、代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 110;
int n;
int g[N][N];    // 邻接矩阵存储图
int st[N];      // 标记顶点是否已在生成树中
int dist[N];    // 存储各顶点到生成树的最小距离

int prim()
{
    int res = 0;  // 存储最小生成树的总权值
    memset(dist, 0x3f, sizeof dist);  // 初始化距离为无穷大
    dist[1] = 0;  // 从1号农场开始

    for (int i = 1; i <= n; i ++)  // 每次循环加入一个顶点
    {
        int t = -1;
        // 找出距离当前生成树最近的一个顶点t
        for (int j = 1; j <= n; j ++)
        {
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }

        res += dist[t];  // 累加边权
        st[t] = 1;       // 标记t已加入生成树

        // 更新其他顶点到生成树的距离
        for (int j = 1; j <= n; j ++)
            dist[j] = min(g[t][j], dist[j]);
    }
    return res;
}

void solve()
{
    memset(g, 0x3f, sizeof g);  // 初始化图
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> g[i][j];
    int ans = prim();
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

六、重点细节

1. 初始化：距离数组dist初始化为无穷大，表示初始时所有顶点都不可达
2. 顶点选择：每次选择距离当前生成树最近的未加入顶点（t）
3. 距离更新：当新顶点t加入后，更新其他顶点到生成树的距离（取最小值）
4. 对称矩阵：题目保证输入是对称矩阵，即g[i][j] = g[j][i]

七、复杂度分析

• 时间复杂度：O(n²)，因为外层循环n次，内层有两个n次循环
• 空间复杂度：O(n²)，用于存储邻接矩阵

八、总结

本题是典型的最小生成树问题，使用Prim算法可以高效解决。算法核心思想是”贪心”，每次选择当前最优的边加入生成树。对于稠密图（边数接近完全图），Prim算法（尤其是这种邻接矩阵实现）是一个不错的选择。