【例4-11】最短网络(agrinet)

题目描述

农民约翰当选镇长后承诺给所有农场连上互联网：已有一条高速线路接入了他的农场，他想用最短的光纤把其余农场都连起来。给出农场个数 N（3≤N≤100）和一个 N×N 矩阵，第 i 行第 j 列表示农场 i 与 j 之间的连接费用（对角线为 0，费用不超过 100000），矩阵实际按 80 字符折行、当作空白分隔的数字流读入。求连接所有农场的光纤最小总长度。

样例输入：4、0 4 9 21、4 0 8 17、9 8 0 16、21 17 16 0

样例输出：28

思路

「连通所有农场且总长最短」就是最小生成树的字面定义，输入又是稠密图的邻接矩阵，所以用与读入同阶的 O(n²) Prim 数组版。维护 dis[j] 为树外点 j 到当前树的最短边权，每轮把距离树最近的树外点拉入树，并用它所在行对其余树外点做一遍取 min 松弛。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 20:30
# update_at: 2026-10-08 20:30

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    g = [[next(data) for _ in range(n)] for _ in range(n)]  # n*n 距离矩阵

    INF = float('inf')
    dis = g[0][:]        # dis[j]：树外点 j 到当前树的最短边长，初始树只有农场 0
    dis[0] = INF         # 农场 0 已在树里，不参与选取
    in_tree = [True] + [False] * (n - 1)  # 点是否已并入生成树
    answer = 0
    for _ in range(n - 1):  # 每轮并入一个点、加一条边，共 n-1 轮
        k = min(range(n), key=dis.__getitem__)  # 距离树最近的树外点 k
        answer += dis[k]
        in_tree[k] = True
        # 用 k 的出边松弛：树外的点取 min，树内的点一律置回 INF 不再参与
        dis = [INF if t else min(d, gk) for d, gk, t in zip(dis, g[k], in_tree)]

    print(answer)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 11:23
 * update_at: 2026-10-05 11:23
 */
#include <cstdio>

typedef long long ll;

const int MAXN = 105;
const ll INF = 0x3F3F3F3F3F3F3F3F;

int n;             // 农场个数
ll g[MAXN][MAXN];  // g[i][j] 表示农场 i 与 j 之间的距离（邻接矩阵）
ll dis[MAXN];      // dis[j] 表示树外点 j 到当前生成树的最短边权；入树后为 INF
bool in_tree[MAXN];// in_tree[j] 表示点 j 是否已进入生成树

int main() {
    scanf("%d", &n);
    // 矩阵按 80 字符折行，逻辑行与物理行不一致，用 token 流读入
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%lld", &g[i][j]);

    // Prim：以 0 号农场为起点，初始只有它在树里
    for (int j = 0; j < n; ++j) dis[j] = g[0][j];
    dis[0] = INF;      // 已入树的点恒为 INF，否则第一轮会重复选中起点
    in_tree[0] = true;

    ll ans = 0;        // 最小生成树的边权总和
    for (int round = 1; round < n; ++round) {
        // 选距离树最近的树外点 k 拉进树（cut 性质保证贪心正确）
        int k = -1;
        for (int j = 0; j < n; ++j)
            if (!in_tree[j] && (k == -1 || dis[j] < dis[k]))
                k = j;
        ans += dis[k];
        in_tree[k] = true;
        dis[k] = INF;

        // 用 k 所在行松弛其余树外点的距离；对角线 g[k][k]=0 不会影响已入树点
        for (int j = 0; j < n; ++j)
            if (!in_tree[j] && g[k][j] < dis[j])
                dis[j] = g[k][j];
    }

    printf("%lld\n", ans);
    return 0;
}

【例4-11】最短网络(agrinet)

目录

题目描述

思路

参考代码