【例4-10】最优布线问题

题目描述

学校有 $n$ 台计算机（ $2 \le n \le 100$ ），要用数据线把它们连通（允许经其它计算机中转），不同两台计算机之间的连接费用不同，求总费用最小的连通方案。输入：第一行 $n$ ，接下来 $n$ 行每行 $n$ 个整数，第 $x$ 行第 $y$ 列表示直接连接第 $x$ 、 $y$ 台计算机的费用。输出：一个整数，即最小连接费用。样例：输入 3 / 0 1 2 / 1 0 1 / 2 1 0，输出 2（连接 1-2 与 2-3，费用 $1+1=2$ ）。

思路

把费用矩阵看成一张完全无向带权图，「所有计算机连通且总费用最小」就是求它的最小生成树。用朴素 Prim：维护 dist[v] 表示已接入点集连到 v 的最便宜边权，每轮取未接入点中 dist 最小的接入并累加费用，再用它那一行松弛其余未接入点， $n$ 轮后得到答案，时间 $O(n^2)$ 。

参考代码

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
33
34
35
36
37
38
39
40#!/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-09-30 06:34
# update_at: 2026-10-04 11:16

import sys

INF = 10**18  # dist 的初值：大于任何合法费用之和，表示暂时没有可用的接入边


def prim(cost: list[list[int]]) -> int:
    """返回费用矩阵所刻画完全图的最小生成树权值和，每轮接入最便宜的可接入点。"""
    n = len(cost)
    dist = [INF] * n        # dist[v] = 已接入点集连到 v 的最便宜一条边的费用
    dist[0] = 0             # 任选顶点 0 当根，接入自己不要钱
    unvisited = set(range(n))
    total = 0

    while unvisited:
        u = min(unvisited, key=dist.__getitem__)  # 最便宜的可接入点：连上它的那条边必须进生成树
        unvisited.remove(u)
        total += dist[u]
        for v in unvisited:  # 接入 u 后，各未接入点的最便宜接入边可能改成走 u
            dist[v] = min(dist[v], cost[u][v])  # 只遍历未接入点，否则 cost[u][u] 的 0 会覆写 dist[u]

    return total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 题面的计算机台数
    # 第 i 行是顶点 i 到各点的费用，按行顺序消费 n×n 个整数
    cost = [[next(data) for _ in range(n)] for _ in range(n)]
    print(prim(cost))


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
52
53
54
55
56
57
58
59
60
61/**
 * 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:15
 * update_at: 2026-10-05 11:15
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 105; // n <= 100，留几个余量
const ll INF = 1e18;  // dist 的初值，大于任何合法费用之和

ll cost[MAXN][MAXN]; // cost[x][y]：直接连接第 x、y 台计算机的费用
ll dist[MAXN];       // dist[v]：已接入点集连到 v 的最便宜一条边的费用
bool used[MAXN];     // used[v]：第 v 台计算机是否已经接入

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n; // 计算机台数
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= n; j++) {
            cin >> cost[i][j];
        }
    }

    // 朴素 Prim：任选 1 号点当起点，接入自己不要钱
    for (ll i = 1; i <= n; i++) {
        dist[i] = INF;
        used[i] = false;
    }
    dist[1] = 0;

    ll ans = 0; // 最小生成树的权值和
    for (ll round = 1; round <= n; round++) {
        // 在未接入点里找 dist 最小的，连它的那条边就是横跨切割的最便宜边
        ll u = 0;
        for (ll v = 1; v <= n; v++) {
            if (!used[v] && (u == 0 || dist[v] < dist[u])) {
                u = v;
            }
        }
        used[u] = true;
        ans += dist[u];
        // 接入 u 后各未接入点可以改走 u 中转；只松弛未接入点，
        // 否则 cost[u][u] = 0 会把自己那行覆盖成 0
        for (ll v = 1; v <= n; v++) {
            if (!used[v] && cost[u][v] < dist[v]) {
                dist[v] = cost[u][v];
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

【例4-10】最优布线问题

目录

题目描述

思路

参考代码