「一本通 3.1 练习 1」新的开始

题目描述

有 $n$ 口矿井，编号 $1 \sim n$ 。两种通电方式：

在第 $i$ 口矿井建发电站，费用 $v_i$ ，一座电站可供给任意多口矿井；
在第 $i$ 、 $j$ 口矿井之间拉电网，费用 $p_{i,j}$ （ $p_{i,j}=p_{j,i}$ ， $p_{i,i}=0$ ）。

要求每口矿井都有电，求最小总花费。 $1 \leqslant n \leqslant 300$ ， $0 \leqslant v_i, p_{i,j} \leqslant 10^5$ 。

输入：第一行 $n$ ；接下来 $n$ 行每行一个 $v_i$ ；然后 $n$ 行每行 $n$ 个整数构成矩阵 $p$ 。
输出：一个整数，最小总花费。

样例输入/输出见 problem.md。

思路

引入超级源点 $S$ ，给每个矿井 $i$ 连一条 $(S,i)$ 边、权为 $v_i$ 。于是建电站和拉电网都变成边，问题转化为在 $n+1$ 个点的完全图上求最小生成树。 $n=300$ 为稠密图，用朴素 Prim $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
41
42
43#!/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 14:15
# update_at: 2026-09-30 14:15

import sys

INF = 10**9  # 哨兵：v_i、p_ij 都不超过 1e5，INF 一定比任何真实边权大


def prim(edge: list[list[int]]) -> int:
    """稠密图最小生成树（Prim + 邻接矩阵）：返回所有点连通的最小总边权。"""
    n = len(edge)
    used = [False] * n
    best = [INF] * n  # 每个未选点连到已选点集的最便宜一条边
    best[0] = 0
    total = 0
    for _ in range(n):
        u = min((best[i], i) for i in range(n) if not used[i])[1]  # 取最便宜的未选点
        used[u] = True
        total += best[u]
        row = edge[u]
        # u 入选后，用 u 连出的边刷新其余未选点的最便宜入边
        for v in range(n):
            if not used[v] and row[v] < best[v]:
                best[v] = row[v]
    return total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    v = [next(data) for _ in range(n)]                 # 各矿井建发电站的费用
    p = [[next(data) for _ in range(n)] for _ in range(n)]  # n×n 电网费用矩阵
    # 超级源点 n：与矿井 i 连一条权 v_i 的边，在 i 建电站 = 选中这条边
    edge = [row + [v[i]] for i, row in enumerate(p)] + [v + [0]]
    print(prim(edge))


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
62
63
64
65
66
67
68/**
 * 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-06 00:23
 * update_at: 2026-10-06 00:23
 */

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 305;
const ll INF = 1e18;

int n;
ll v[MAXN];           // 各矿井建发电站的费用
ll p[MAXN][MAXN];     // 电网费用矩阵
ll edge[MAXN][MAXN];  // 拼成 (n+1) 个点的邻接矩阵，下标 0~n，点 n 为超级源点
bool used[MAXN];      // 是否已加入生成树
ll best[MAXN];        // 未选点连到已选点集的最便宜边权

// 稠密图最小生成树：朴素 Prim，返回总边权
ll prim(int tot) {
    for (int i = 0; i < tot; ++i) {
        used[i] = false;
        best[i] = INF;
    }
    best[n] = 0; // 从超级源点（编号 n）出发
    ll total = 0;
    for (int _ = 0; _ < tot; ++_) {
        int u = -1;
        for (int i = 0; i < tot; ++i)
            if (!used[i] && (u == -1 || best[i] < best[u]))
                u = i;
        used[u] = true;
        total += best[u];
        for (int i = 0; i < tot; ++i)
            if (!used[i] && edge[u][i] < best[i])
                best[i] = edge[u][i];
    }
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> v[i];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> p[i][j];

    // 把超级源点放在下标 n，对应 edge 的第 n 行/列
    // edge[i][j] = p[i][j]（0<=i,j<n），edge[i][n] = edge[n][i] = v[i]
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            edge[i][j] = p[i][j];
    for (int i = 0; i < n; ++i) {
        edge[i][n] = v[i];
        edge[n][i] = v[i];
    }
    edge[n][n] = 0;

    cout << prim(n + 1) << "\n";
    return 0;
}

「一本通 3.1 练习 1」新的开始

目录

题目描述

思路

参考代码