25D 用并查集从无权图中选出一片生成森林，但任意森林都可以，因为边没有成本。1245D 增加了真正的取舍：一座城市可以自己建电站，也可以铺电线接入另一座已经供电的城市；我们要同时决定电站位置和电线，令总费用最小。

表面上这是两类操作。关键建模是增加一个虚拟顶点 0，把“在城市 i 建电站”也变成一条普通边。两类选择进入同一张图之后，问题就成为最小生成树。

1. 官方信息与约束

1245D · Shichikuji and Power Grid 官方题目 于 2026-09-10 核对：难度 1900，官方标签为 dsu、graphs、greedy、shortest paths、trees，时间限制 2 秒，内存限制 256 MB。

题目给出 n 座城市的坐标。城市 i 自建电站费用为 cᵢ；城市 i、j 之间铺线的费用为：

1
(|xᵢ-xⱼ| + |yᵢ-yⱼ|) × (kᵢ+kⱼ)

输出最小总费用、建站城市和所选城市连线。

官方约束 对实现的影响
1 ≤ n ≤ 2000 完全图约有两百万条城市边，可以显式生成并排序
坐标 1…10⁶ 曼哈顿距离最大约 2×10⁶
cᵢ,kᵢ ≤ 10⁹ 单条电线费用可达约 4×10¹⁵
不同城市坐标可以相同 城市间可能存在费用为 0 的电线
输出任意一个最优方案 验证应检查费用和供电性，而非固定答案顺序

总成本也可能超过 32 位整数，距离、边权和答案都必须使用 long long。先转为 64 位再做减法、绝对值和乘法，可以避免中间结果在 int 中溢出。

2. 为什么逐城选择便宜方案会失败

一种直觉是：对每座城市，比较“自建电站”与“接到某个城市”的最低费用，选择较小者。但局部最便宜的电线未必把它接到一个最终有电的区域；多座城市还可能互相选择，形成没有电站的环。

例如三座城市的建站费用都为 10，三条城市连线费用都为 1。逐城都更愿意选电线，但只选电线的三角形没有电源。正确最优方案是建一座电站，再选两条电线，总费用 12。

另一个极端是先决定所有建站点，再对其余城市找连接。这样需要枚举 2ⁿ 个建站集合。问题缺少的不是更聪明的局部比较，而是把“建站”与“连线”放进同一种连通结构。

3. 虚拟源点：把建站也画成边

新增顶点 0，代表一个抽象的电力来源：

  • 对每座城市 i，加入边 (0,i)，权重为 cᵢ；选中它表示在 i 建电站。
  • 对每对城市 i、j，加入边 (i,j)，权重为铺线费用；选中它表示修建这条电线。

在扩展图中，所有城市有电等价于所有城市都能走到 0：路径上遇到的第一条 0—i 边就是某座电站，后面的城市通过所选电线接入它。

4. 为什么最优方案一定可以是一棵树

先证明两个方向，避免只凭图像宣布“这是 MST”。

从供电方案到连通子图。 给定任意可行方案，把每座电站替换为一条 0—i 边，把每条电线保留为城市边。每座城市都能沿供电关系到达某座电站，因此扩展图中的所有顶点与 0 连通。

从连通子图到供电方案。 反过来，扩展图若连通，删除虚拟顶点的外壳含义，把与 0 相连的边解释为电站，其余边解释为电线。每座城市都有一条到 0 的路径，因此都能从路径上的某座电站获得电力。

所有费用非负。任何连通子图若有环，删掉环上一条边仍然连通，成本不会增加。持续删环后得到一棵覆盖 0…n 的生成树。因此至少存在一个最优供电方案对应扩展图的最小生成树。

这也解释了为什么一座城市可以通过多级电线获得电力：树上的路径本来就允许多个中间顶点。

5. Kruskal：从最便宜的边开始，但必须有证明

将全部边按权重升序排列。扫描边 (u,v)：

  • 若 u、v 属于不同集合，选择该边并合并集合；
  • 若已经连通，跳过该边，避免成环；
  • 选满 n 条边后停止，因为扩展图有 n+1 个顶点。

割性质证明。 在某次选择前，并查集的每个集合是当前森林的一个连通块。Kruskal 选择的是跨越这些块的全局最轻边 e。取任意包含此前已选边的最小生成树 T：若 T 已含 e，无需改变；否则把 e 加入 T 会形成一个环。环上必有另一条边 f 跨越 e 所连接的两个当前块，而且 w(e)≤w(f)。用 e 替换 f 后仍是生成树，成本不增，并包含更多 Kruskal 已选边。归纳可知所有选择都能扩展为某棵 MST。

相同权重的边可以任意排序，交换论证仍成立，所以不同正确程序可能输出不同方案。

6. 手工演算

取三个城市，坐标、建站费用与系数如下：

城市 坐标 建站费用 c 系数 k
1 (1,1) 3 1
2 (2,1) 8 1
3 (5,1) 4 1

扩展图的边权为：

边 含义 费用
0—1 城市 1 建站 3
0—2 城市 2 建站 8
0—3 城市 3 建站 4
1—2 距离 1，系数和 2 2
1—3 距离 4，系数和 2 8
2—3 距离 3，系数和 2 6

按费用扫描：

顺序 边 决策 已选总费用 连通块
1 1—2，2 选择 2 {1,2}、{0}、{3}
2 0—1，3 选择，城市 1 建站 5 {0,1,2}、{3}
3 0—3，4 选择，城市 3 建站 9 全部连通

最终在城市 1、3 建站，并铺设 1—2，费用 9。若只建城市 1 的电站再铺 1—2、2—3，费用为 11；“电站越少越好”并不是目标。

7. 完整 C++17 实现

边结构中将权重放在前面只是为了排序方便。输出时，虚拟边与城市边分开保存。

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
using namespace std;

using int64 = long long;

struct DSU {
    vector<int> parent, size;
    explicit DSU(int n) : parent(n), size(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int v) {
        if (parent[v] != v) parent[v] = find(parent[v]);
        return parent[v];
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
        return true;
    }
};

struct Edge {
    int64 cost;
    int u, v;
    bool operator<(const Edge& other) const {
        return cost < other.cost;
    }
};

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

    int n;
    cin >> n;
    vector<int64> x(n + 1), y(n + 1), c(n + 1), k(n + 1);
    for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i];
    for (int i = 1; i <= n; ++i) cin >> c[i];
    for (int i = 1; i <= n; ++i) cin >> k[i];

    vector<Edge> edges;
    edges.reserve(static_cast<size_t>(n) * (n + 1) / 2);
    for (int i = 1; i <= n; ++i) edges.push_back({c[i], 0, i});
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            const int64 distance = llabs(x[i] - x[j]) + llabs(y[i] - y[j]);
            edges.push_back({distance * (k[i] + k[j]), i, j});
        }
    }
    sort(edges.begin(), edges.end());

    DSU dsu(n + 1);
    int selected = 0;
    int64 total = 0;
    vector<int> stations;
    vector<pair<int, int>> wires;
    for (const Edge& edge : edges) {
        if (!dsu.unite(edge.u, edge.v)) continue;
        total += edge.cost;
        ++selected;
        if (edge.u == 0) stations.push_back(edge.v);
        else wires.emplace_back(edge.u, edge.v);
        if (selected == n) break;
    }

    cout << total << '\n';
    cout << stations.size() << '\n';
    for (int city : stations) cout << city << ' ';
    cout << '\n';
    cout << wires.size() << '\n';
    for (auto [u, v] : wires) cout << u << ' ' << v << '\n';
    return 0;
}

8. 复杂度与内存估算

扩展图有 E=n+n(n−1)/2=n(n+1)/2 条边。生成边为 O(n²)，排序为 O(n² log n)，并查集扫描为 O(n² α(n))；总时间由排序主导。边数组占 O(n²) 空间。

当 n=2000 时共有 2,001,000 条边。上述 Edge 通常占 16 字节，约需 32 MB；再加排序、坐标和并查集数组，低于 256 MB。不过结构体实际大小由实现与对齐决定，内存估算不应只数逻辑字段。

这道题还可用 O(n²) 的 Prim，不必保存完整边集。本文使用 Kruskal，是为了承接 25D 的并查集路线；若约束进一步增大，显式完全图会先在内存和排序上成为瓶颈。

9. 边界与错误清单

易错点 后果 检查方式
把“建站”单独贪心决定 无法统一比较电站与连线 加虚拟顶点 0
只让电站城市彼此连通 其他城市可能没有到电站的路径 检查扩展图全部 n+1 个点连通
城市边费用漏乘系数和 权重模型错误 手算一条曼哈顿距离边
用 int 计算乘法 单边即可能溢出 坐标和系数读入 long long
认为坐标相同就是同一城市 会漏掉合法的 0 费用边 城市编号仍然不同
选中 0—i 后输出为电线 输出格式错误 虚拟边归入 stations
只选 n−1 条边 扩展图有 n+1 个点 MST 恰好选择 n 条边
忘记 n=1 仍需建一个电站 扩展图选择唯一的 0—1 边

10. 独立验证

验证脚本 tests/verify-power-grid-article.cjs 直接提取本文 C++17 代码，无警告编译。它会解析输出并逐项检查：电站不重复、连线端点有效、所报成本与方案成本一致、所有城市最终连到某个电站。

最优值由独立的 O(n²) Prim 计算，不复用文章的边排序或并查集。测试包含 n=1、相同坐标、极大费用、手工例子、固定种子随机数据，以及 n=2000 的规模测试。不同 MST 的输出可能不同，所以只比较可行性与最优总费用。

完成后回到 算法练习路径：25D 训练“合并不同集合”，1245D 在此基础上加入边权顺序和割性质。下一步可以学习树上 DFS，分析一棵已经选出的树；也可以进入更难的 MST 边分类问题。