Shichikuji and Power Grid

GitHub跳转原题关系图返回列表

加虚拟源点把「建电站」变成一条边，答案成为 n+1 个点的最小生成树；稠密完全图上选 O(n²) 的 Prim 现场扫描，不落地保存两百万条边。

OJ: codeforces

题目 ID: 1245D

难度:普及+/提高-

标签:图论最小生成树建模贪心

创建: 2026-10-21 20:00

更新: 2026-10-28 17:33

形式化题目

平面上有 $n$ 个城市，第 $i$ 个位于整点 $(x_i, y_i)$ （可能重合）。每个城市必须以下面两种方式之一获得电力：

在城市 $i$ 建电站，花费 $c_i$ ；
与另一个已经有电的城市 $j$ 之间拉一条电线，花费

(k_i + k_j) \cdot \bigl(|x_i - x_j| + |y_i - y_j|\bigr),

即两端系数之和乘以曼哈顿距离（不是 $k$ 值相加，也不是取较大者）。

电力可以沿电线传递。求让所有城市通电的最小总花费，并给出方案：建电站的城市列表和拉线的城市对列表。

一个合法方案的结构是：选出若干城市建电站，其余每个城市通过拉线链最终连到某个电站城市——即若干棵以电站城市为根的树互不重叠地覆盖所有 $n$ 个城市。

暴力解法

思路

最直接的想法分两层：先枚举「哪些城市建电站」，再在固定电站集合后决定「其余城市怎么连」。

第一层用子集枚举：设 $S$ 是建电站的城市集合。固定 $S$ 之后有一个关键观察：拉线只能架在城市之间，把线连到最终不用电的位置只会白白花钱，所以最优拉线方案中所有边都落在同一个连通块内。于是固定 $S$ 后的最优方案就是——以 $S$ 为根集合、覆盖全部 $n$ 个城市的最小生成森林。

求这个森林只需一次朴素 Prim：把 $S$ 中的城市视为已免费「入树」，每个未入树城市的初始距离是它到最近电站城市的拉线代价，每轮把距离最小的城市连进来并刷新其余城市， $O(n^2)$ 完成。

总复杂度 $O(2^n \cdot n^2)$ ， $n \leqslant 14$ 左右可以跑完，足够做小数据对拍。

代码

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91/**
 * 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-21 20:00
 * update_at: 2026-10-21 20:00
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 真正的暴力：枚举「哪些城市建电站」的所有子集 S（01 枚举），
// 固定 S 后，最优拉线方案 = 以 S 中城市为根、覆盖所有城市的最小生成森林，
// 也就是「T 中城市 = 全部城市」时把 S 看作已免费连通再对其余城市做 Prim。
// 复杂度 O(2^n * n^2)，只适合 n <= 14 左右的小数据，与 main.cpp 不共享实现。
// 注意：输出只有最小花费，用于与主解对拍数值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 16;
ll n;
ll x[maxn], y[maxn]; // 城市坐标
ll c[maxn];         // c[i]：在城市 i 建电站的花费
ll k[maxn];         // k[i]：拉线时每公里付出的系数

// 城市 i 与 j 之间拉线的代价：(k_i + k_j) * 曼哈顿距离
ll wire_cost(ll i, ll j) {
    return (k[i] + k[j]) * (abs(x[i] - x[j]) + abs(y[i] - y[j]));
}

// 固定建电站集合 mask（第 i-1 位为 1 表示城市 i 建电站）后的最优总花费：
// 电站城市视为已通电，其余城市用最小生成森林的方式连进来。
// 朴素 Prim：dist[i] 是未入树城市 i 到「已通电集合」的最小拉线代价。
ll forest_cost(ll mask) {
    ll station_cost = 0;
    for (ll i = 1; i <= n; i++)
        if (mask >> (i - 1) & 1) station_cost += c[i];

    ll dist[maxn];      // dist[i]：城市 i 到已通电集合的最小拉线代价
    bool in_tree[maxn]; // in_tree[i]：城市 i 是否已通电（含建电站的城市）
    for (ll i = 1; i <= n; i++) {
        in_tree[i] = mask >> (i - 1) & 1;
        dist[i] = 0;
    }
    // 非电站城市初始只能直接连到某个电站城市：取到最近电站的拉线代价
    for (ll i = 1; i <= n; i++)
        if (!in_tree[i]) {
            dist[i] = -1; // -1 作为无穷哨兵
            for (ll s = 1; s <= n; s++)
                if (in_tree[s]) {
                    ll cost = wire_cost(s, i);
                    if (dist[i] == -1 || cost < dist[i]) dist[i] = cost;
                }
        }
    ll wire_total = 0;
    ll left = n;
    for (ll i = 1; i <= n; i++)
        if (in_tree[i]) left--;
    while (left > 0) { // 每轮把离已通电集合最近的城市连进来
        ll best_i = 0;
        for (ll i = 1; i <= n; i++)
            if (!in_tree[i] && (best_i == 0 || dist[i] < dist[best_i]))
                best_i = i;
        in_tree[best_i] = true;
        wire_total += dist[best_i];
        left--;
        for (ll i = 1; i <= n; i++)
            if (!in_tree[i]) {
                ll cost = wire_cost(best_i, i); // 新通电城市刷新其余城市的最近距离
                if (cost < dist[i]) dist[i] = cost;
            }
    }
    return station_cost + wire_total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> x[i] >> y[i];
    for (ll i = 1; i <= n; i++) cin >> c[i];
    for (ll i = 1; i <= n; i++) cin >> k[i];

    // 枚举所有建电站子集：城市 1..n 的建/不建构成 01 序列，mask 的第 i-1 位即城市 i
    ll best = -1; // 最优总花费，-1 表示还没有答案
    for (ll mask = 1; mask < (1LL << n); mask++) { // 至少建一个电站
        ll total = forest_cost(mask);
        if (best == -1 || total < best) best = total;
    }
    if (n == 0) best = 0;
    cout << best << "\n";
    return 0;
}

复杂度

时间 $O(2^n \cdot n^2)$ ，空间 $O(n)$ 。只适合小数据。

瓶颈

暴力的两层结构把「谁建电站」和「谁连谁」当成互相独立的枚举： $2^n$ 个电站子集里绝大多数明显劣等，我们却要为每一个都跑一遍 Prim。真正的问题是——建电站这个「点上的决策」和拉线这个「边上的决策」没有统一的表达，只能分层枚举。下一节把两者变成同一种东西。

正解

思路

虚拟源点建模：新增一个点 $S$ ，把两种操作统一成边：

操作	对应的边	边权
在城市 $i$ 建电站	$S \to i$	$c_i$
城市 $i, j$ 之间拉线	$i \leftrightarrow j$	$(k_i + k_j) \cdot \text{dist}(i, j)$

这张表是全部建模：左列是题目里的操作，右列是 $n+1$ 个点的图上的边，权值一一相同。

「所有城市通电」等价于「 $S$ 与每个城市连通」，也就是 $S$ 所在的连通块覆盖全部 $n+1$ 个点。在这张图上取 $n+1$ 个点的最小生成树即可。

与合法方案的双向等价（这是正确性的核心，两个方向都要成立）：

方案 → 生成树：把方案里每个「城市 $i$ 建电站」替换成边 $S \to i$ ，每条拉线替换成对应边。方案合法 ⟺ 每个城市建站或沿拉线链到达电站 ⟺ 替换后的 $n$ 条边让 $n+1$ 个点全部连通，而 $n$ 条边连通 $n+1$ 个点必无环，故是生成树。总花费逐条相等。
生成树 → 方案：读出 $S$ 的邻边得到电站集合，其余树边作为拉线。每个非 $S$ 的点沿树中唯一路径走向 $S$ ，路径第一条边必是某条 $S \to i$ 电站边，因此每个城市要么自己建站、要么连着一个最终有电的城市。总花费同样逐条相等。

两个方向的花费都严格相同，所以「最小花费的合法方案」与「最小生成树」一一对应，MST 算法输出的树直接翻译成题目要求的输出格式。

为什么能在建电站和拉线之间自由选择：MST 每一步只看当前最小边，不区分它是电站边还是拉线边。 $c_i$ 小的城市自动建站， $k$ 小、距离近的城市对自动拉线；如果某条拉线在后面的轮次变得比建站贵，Prim 的 dist 数组会自然被更便宜的电站边覆盖。两种操作在同一棵树上竞争，不需要任何分类讨论——这正是把「点决策」也变成「边」的回报。

实现选择： $O(n^2)$ 的 Prim，而不是 Kruskal。 $n \leqslant 2000$ 时建电站边加城市间完全图约有 $n^2/2 = 2 \times 10^6$ 条边。Kruskal 必须真的把这二百万条边生成、存下来再排序， $O(E \log E)$ 在时限边缘，内存也要几十 MB。稠密完全图上的标准结论是改用 $O(n^2)$ 的 Prim：不存边表、不用并查集，每轮 $O(n)$ 现场扫描选出 dist 最小的未入树点，再用它刷新其余点的 dist，总共约 $4 \times 10^6$ 次基本操作。实测 $n = 2000$ 满规模数据：C++ 约 0.02s，Python 约 1.4s，都非常安全。

Prim 还免费送了输出方案：from[i] 记录 dist[i] 这条边的另一端，from[i] = 0（虚拟源点）说明是电站边，否则是拉线边，逐点分类即可。注意数值上 $n$ 条边、每条至多约 $4 \times 10^{15}$ ，总和在 long long 范围内。

Python 版是同一算法的实现，读入用 next() 顺序消费，内层循环写紧凑即可。

代码

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84/**
 * 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-21 20:00
 * update_at: 2026-10-21 20:00
 */
// CF1245D Shichikuji and Power Grid
// 建模：加虚拟源点 0，0->i 边权 c_i（建电站），i->j 边权 (k_i+k_j)*曼哈顿距离（拉线），
// 答案 = n+1 个点的最小生成树。
// n <= 2000 时完全图约有 2*10^6 条边，对它们排序的 Kruskal 在时限边缘；
// 这里用 O(n^2) 的 Prim：每轮 O(n) 现场扫描选最近点，不落地保存任何边。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2005;
ll n;
ll x[maxn], y[maxn];   // 城市坐标
ll c[maxn];            // c[i]：在城市 i 建电站的花费
ll k[maxn];            // k[i]：拉线时每公里付出的系数

ll dist[maxn];         // dist[i]：城市 i 到"当前已通电集合"的最小边权（初始为建电站代价 c_i）
int from[maxn];        // from[i]：dist[i] 对应的边的另一端，0 表示"建电站"这条虚拟边
bool used[maxn];       // used[i]：城市 i 是否已并入生成树

// 城市 i 与 j 之间拉线的代价：(k_i + k_j) * 曼哈顿距离
ll wire_cost(ll i, ll j) {
    return (k[i] + k[j]) * (abs(x[i] - x[j]) + abs(y[i] - y[j]));
}

vector<ll> stations;              // 建电站的城市编号（对应树里 0->i 的边）
vector<pair<ll, ll>> connections; // 拉线的城市对（对应树里 i->j 的边）

void prim() {
    // 初始所有点都未加入，到集合的最近距离就是"建电站"这条虚拟边的权
    for (ll i = 1; i <= n; i++) {
        dist[i] = c[i];
        from[i] = 0; // 0 是虚拟源点：先默认每个城市自己建电站
    }
    for (ll round = 1; round <= n; round++) { // 一共要把 n 个城市全部并入
        // 找到未加入城市中 dist 最小的一个
        ll best = 0;
        for (ll i = 1; i <= n; i++)
            if (!used[i] && (best == 0 || dist[i] < dist[best]))
                best = i;
        used[best] = true;
        if (from[best] == 0)
            stations.push_back(best);               // 与虚拟源点相连：建电站
        else
            connections.push_back({from[best], best}); // 与已有城市相连：拉线
        // 新点并入后，用它的出边更新其余城市的最近距离
        for (ll i = 1; i <= n; i++)
            if (!used[i] && wire_cost(best, i) < dist[i]) {
                dist[i] = wire_cost(best, i);
                from[i] = best;
            }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> x[i] >> y[i];
    for (ll i = 1; i <= n; i++) cin >> c[i];
    for (ll i = 1; i <= n; i++) cin >> k[i];

    prim();

    ll total = 0;
    for (ll s : stations) total += c[s];
    for (auto e : connections)
        total += wire_cost(e.first, e.second);

    cout << total << "\n";
    cout << stations.size() << "\n";
    for (ll i = 0; i < (ll)stations.size(); i++)
        cout << stations[i] << " \n"[i + 1 == (ll)stations.size()];
    cout << connections.size() << "\n";
    for (ll i = 0; i < (ll)connections.size(); i++)
        cout << connections[i].first << " " << connections[i].second << "\n";
    return 0;
}

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
44
45
46
47
48
49
50
51
52#!/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-21 20:00
# update_at: 2026-10-21 20:00

import sys

INF = float("inf")  # 已加入城市的 dist 哨兵，让 min 扫描自动跳过它们


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    pairs = [(next(data), next(data)) for _ in range(n)]  # (x_i, y_i) 成对读入
    X = [px for px, _ in pairs]  # 题面的 x_i，下标 0..n-1 对应城市 1..n
    Y = [py for _, py in pairs]
    C = [next(data) for _ in range(n)]  # 建电站代价
    K = [next(data) for _ in range(n)]  # 拉线系数

    def wire_cost(i: int, j: int) -> int:
        """城市 i 与 j 之间拉线的代价：(k_i + k_j) * 曼哈顿距离。"""
        return (K[i] + K[j]) * (abs(X[i] - X[j]) + abs(Y[i] - Y[j]))

    # Prim：dist[i] 是城市 i 到已并入集合的最近边权，初始为“建电站”虚拟边 c_i。
    dist = C[:]
    source = [None] * n  # source[i]：dist[i] 这条边的另一端城市，None 表示建电站
    joined = [False] * n
    stations: list[int] = []
    connections: list[tuple[int, int]] = []
    for _ in range(n):  # 每轮并入一个城市，共 n 轮
        best = min(range(n), key=lambda i: INF if joined[i] else dist[i])
        joined[best] = True
        if source[best] is None:
            stations.append(best + 1)  # 树里挂在虚拟源点下：这个城市建电站
        else:
            connections.append((source[best] + 1, best + 1))
        for i in range(n):
            cost = wire_cost(best, i)  # 新点并入后用它刷新其余城市的最近距离
            if not joined[i] and cost < dist[i]:
                dist[i] = cost
                source[i] = best

    total = sum(C[s - 1] for s in stations) + sum(wire_cost(a - 1, b - 1) for a, b in connections)
    out = [str(total), str(len(stations)), " ".join(map(str, stations)), str(len(connections))]
    out += [f"{a} {b}" for a, b in connections]
    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

时间 $O(n^2)$ （ $n = 2000$ 时约 $4 \times 10^6$ 次内层操作），空间 $O(n)$ ——不需要存任何一条边。

总结

本题全部内容浓缩在一个建模：加虚拟源点 $S$ ，「建电站」变成边 $S \to i$ （权 $c_i$ ），「拉线」变成边 $i \leftrightarrow j$ （权 $(k_i + k_j) \cdot$ 曼哈顿距离），答案就是 $n+1$ 个点的最小生成树。
读题时最危险的一处是拉线代价乘了曼哈顿距离；建模时最关键的一步是意识到「点上的建站决策」也能表达成一条边，从而消除暴力里 $2^n$ 层的电站枚举。
稠密完全图上， $O(n^2)$ 的 Prim 现场扫描优于「生成两百万条边再排序」的 Kruskal，时间和内存都更稳。
验证记录：官方样例 in1/in2 两实现花费与官方一致（ $8$ 、 $27$ ）且方案通过校验器；gen.py 以 tiny（ $n=1$ ）、small_c（电站都便宜）、big_k（拉线都贵）、dup_pos（坐标压到 $2 \times 2$ 强制重复）、normal 五种模式生成 320 组小数据，main.cpp 与 main.py 的输出全部通过自洽校验器（花费 = 电站代价之和 + 拉线代价之和、索引合法、无重复无自环、所有城市连通），且两者的最小花费均与 brute.cpp 的最优值一致，320/320 通过；另有 $n = 2000$ 、值域全上限随机的满规模数据一组，两实现花费一致且校验通过。因答案不唯一（电站顺序、并列最优解均可不同），正式判定使用校验器而非逐字节比对。

1245D Shichikuji and Power Grid

题目描述

七苦地是南黑蜗牛寺的新任守护神。她的第一项任务如下：

在X县有 $n$ 座新城市，城市编号从 $1$ 到 $n$ 。第 $i$ 号城市位于神社正北 $x_i$ 公里，正东 $y_i$ 公里处。即使 $(x_i, y_i) = (x_j, y_j)$ ，也可能出现 $i \ne j$ 的情况。

七苦地需要给每个城市供电，方法是要么在该城市建电站，要么将该城市与已有电力的城市连接起来。只要城市本身有电站，或者通过一条或多条连接链路与有电站的城市相连，该城市就算通电。

在第 $i$ 号城市建电站需要花费 $c_i$ 日元；
连接第 $i$ 号城市和第 $j$ 号城市的线路费用为每公里 $k_i + k_j$ 日元。线路只能沿着正北、正南、正东、正西方向铺设，线路可以相交。每条线路的两端必须连接两个城市。如果第 $i$ 号城市和第 $j$ 号城市之间有线路，那么该线路会沿着第 $i$ 号城市到第 $j$ 号城市的任意一条最短路径铺设。因此，连接第 $i$ 号城市和第 $j$ 号城市的线路长度为 $|x_i - x_j| + |y_i - y_j|$ 公里。

七苦地想尽可能少花钱完成这项工作，因为她觉得世界上除了钱啥都不值钱。但她只上到五年级，脑子不够灵光，所以请你帮帮她。

所以，你需要告诉七苦地：给所有城市供电所需的最少日元数，在哪些城市建电站，以及需要铺设哪些线路。

如果有多种方案都能达到最低费用，输出其中任意一种即可。

输入格式

第一行输入一个整数 $n$ ( $1 \leq n \leq 2000$ )，表示城市数量。

接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i$ ( $1 \leq x_i \leq 10^6$ ) 和 $y_i$ ( $1 \leq y_i \leq 10^6$ )，表示第 $i$ 个城市的坐标。

接下来一行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ( $1 \leq c_i \leq 10^9$ )，表示在第 $i$ 个城市建电站的费用。

最后一行包含 $n$ 个整数 $k_1, k_2, \dots, k_n$ ( $1 \leq k_i \leq 10^9$ )。

输出格式

第一行输出一个整数，表示供电所需的最少日元数。

接着输出一个整数 $v$ ，表示建电站的城市数量。

然后输出 $v$ 个整数，表示在哪些城市建电站。每个数字在 $1$ 到 $n$ 之间，且互不相同。顺序随意。

接着输出一个整数 $e$ ，表示需要铺设的线路数量。

最后输出 $e$ 对整数 $a$ 和 $b$ ( $1 \le a, b \le n$ , $a \ne b$ )，表示连接第 $a$ 号城市和第 $b$ 号城市。每对城市最多出现一次（对于每个 $(a, b)$ ，不允许有多于 $(a, b)$ 或 $(b, a)$ 的重复连接）。顺序随意。

如果有多种方案都能达到最低费用，输出其中任意一种即可。

说明

样例答案对应的示意图如下（建有电站的城市用绿色标出，其他城市用蓝色，线路用红色）：

第一个样例中，在所有城市都建电站的费用是 $3 + 2 + 3 = 8$ 。可以证明没有比花费8日元更便宜的方案。

第二个样例中，在第2号城市建电站花费2日元。连接第1号和第2号城市的线路费用是 $2 \cdot (3 + 2) = 10$ ，连接第2号和第3号城市的线路费用是 $3 \cdot (2 + 3) = 15$ 。因此总费用是 $2 + 10 + 15 = 27$ 。可以证明没有比27日元更便宜的方案。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

Shichikuji and Power Grid

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

代码

复杂度

总结