最短网络 Agri-Net

最小生成树 T2 P1546 [USACO3.1]最短网络 Agri-Net - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目背景

Farmer John 被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。

题目描述

FJ 已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过 $10^5$。

输入格式

第一行农场的个数 $N$（$3\le N\le 100$）。

接下来是一个 $N\times N$ 的矩阵，表示每个农场之间的距离。理论上，他们是 $N$ 行，每行由 $N$ 个用空格分隔的数组成，实际上，由于每行 $80$ 个字符的限制，因此，某些行会紧接着另一些行。当然，对角线将会是 $0$，因为不会有线路从第 $i$ 个农场到它本身。

输出格式

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

样例 #1

样例输入 #1

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

样例输出 #1

28

思路

在一个无向图内求出将所有点连通起来的最小权值和, 也就是最小生成树。

通常有两个算法：

• Prim算法
  1. 建完图后进行类似dijkstra的操作
  2. 循环n-1次, 每次使用当前权值最小的点, 更新它能到的所有点
• Kruskal算法
  1. 对所有边排序
  2. 创建一个并查集, 然后从小到大遍历所有边
  3. 若当前边的两个点不在一个集合内, 就将其合并, 并加上该边的权值

其中Prim的复杂度是 $O(n^2)$, Kruscal的复杂度是 $O(m\log m)$ 。 一般稀疏图用Kruscal, 稠密图用Prim, 不过大部分情况下用Kruscal都可以。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
 
const int N = 120;
int g[N][N];
int dist[N];
bool st[N];
int n;
 
int prim()
{
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    dist[1] = 0;
    for (int i = 1; i <= n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        st[t] = true;
        res += dist[t];
 
        for (int j = 1; j <= n; j++)
            if (g[t][j])
                dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> g[i][j];
    cout << prim();
 
    return 0;
}