[USACO08OCT] Watering Hole G

形式化题目

有 $n$ 个点表示田地，并有两种"获取水"的手段：

在第 $i$ 个点打井，一次性花 $W_i$ ；
在点 $i$ 与点 $j$ 之间铺一根水管，花 $P_{ij}$ ，且 $P_{ij}=P_{ji}$ 。

选一个打井的点集与一个铺管的边集，要求每个点都满足：它自己打了井，或者沿着已铺的水管能走到某个打了井的点。求总花费的最小值。

注意两种手段的地位并不对称：铺管只能"借用"已经有的水，打井才能凭空产生水。这个不对称正是本题建模的难点，也是后面引入虚拟源点的动机。

样例： $W=(5,4,4,3)$ ，水管费用矩阵中 $1\text{-}2,1\text{-}3,1\text{-}4$ 都是 $2$ ， $2\text{-}3,2\text{-}4$ 是 $3$ ， $3\text{-}4$ 是 $4$ 。答案是 $9$ ：在 $4$ 号田打井（ $3$ ），再铺 $1\text{-}4$ 、 $1\text{-}2$ 、 $1\text{-}3$ 三根管（ $2+2+2$ ）。

暴力解法

思路

按定义直接枚举决策。方案由两部分拼成：

哪些田打井，共 $2^n$ 种；
哪些田之间铺管，共 $m=\frac{n(n-1)}{2}$ 根候选管， $2^m$ 种。

一个完整的方案（先选一个打井集合 $J$ ，再选一个水管集合 $E'$ ）是否合法，判据是：把选中的管子连起来，每个连通块里至少要有一口井。因为块内任意两块田能互相走通，只要块内有一口井，全块都有水；块内一口井都没有，这个块就是干的。

于是用一个 01 序列递归枚举"第 $e$ 根管子选不选"，到叶子时用并查集把选中的管子并成连通块，再检查每个连通块的井标记。

代码

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116/**
 * 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 10:20
 * update_at: 2026-10-21 10:20
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 做法：直接枚举"哪些田打了井"（共 2^n 种），再枚举"选了哪些水管"（共 2^m 种，m = n(n-1)/2），
// 对每个完整方案检查"每个只连水管的连通块里都至少有一口井"，合法就更新最小花费。
// 复杂度 2^n * 2^m，n = 5 时约 3.3 万，n = 6 时约 200 万，所以只适合很小的数据；
// 它完全没有用到虚拟源点和最小生成树，因此可以和 main.cpp 独立对拍。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10;   // 田地数上限，只服务小数据（下标 1..n，含 0 号位）
const int MAXM = 60;   // 水管边数上限，n = 10 时 m = 45
const ll INF = 1000000000;  // 足够大的"无穷"，答案最大约 n * max(W_i) = 8e5

int n;                 // 田地数
ll well_cost[MAXN];    // well_cost[i]：在第 i 块田打井的花费 W_i
ll pipe_cost[MAXN][MAXN];  // pipe_cost[i][j]：第 i、j 块田之间铺水管的费用 P_ij

int edge_u[MAXM];      // edge_u[e]：第 e 条水管的一端
int edge_v[MAXM];      // edge_v[e]：第 e 条水管的另一端
ll edge_w[MAXM];       // edge_w[e]：第 e 条水管的费用
int edge_cnt;          // 水管条数 m

int choose_edge[MAXM]; // 01 序列：choose_edge[e] = 1 表示选了第 e 条水管

ll best_cost;          // 当前搜到的最小花费

int dsu_parent[MAXN];  // 并查集父节点，只在 check() 里临时用

int dsu_find(int x) {
    while (dsu_parent[x] != x) {
        dsu_parent[x] = dsu_parent[dsu_parent[x]];
        x = dsu_parent[x];
    }
    return x;
}

// 判断当前方案是否合法：把选了的水管连起来，每个连通块里至少要有一口井。
bool check(int well_mask) {
    for (int i = 1; i <= n; i++) dsu_parent[i] = i;
    for (int e = 1; e <= edge_cnt; e++) {
        if (!choose_edge[e]) continue;
        int root_a = dsu_find(edge_u[e]);
        int root_b = dsu_find(edge_v[e]);
        if (root_a != root_b) dsu_parent[root_b] = root_a;
    }

    // has_well[root] 记录这个连通块里有没有井
    bool has_well[MAXN] = {false};
    for (int i = 1; i <= n; i++) {
        int root = dsu_find(i);
        if ((well_mask >> (i - 1)) & 1) has_well[root] = true;
    }
    for (int i = 1; i <= n; i++) {
        if (!has_well[dsu_find(i)]) return false;  // 这一块没水
    }
    return true;
}

// 一层在做一件事：决定第 dep 条水管选还是不选。
void dfs_choose_edge(int dep, int well_mask, ll well_sum, ll pipe_sum) {
    if (dep > edge_cnt) {
        if (check(well_mask) && well_sum + pipe_sum < best_cost) {
            best_cost = well_sum + pipe_sum;
        }
        return;
    }
    choose_edge[dep] = 0;
    dfs_choose_edge(dep + 1, well_mask, well_sum, pipe_sum);
    choose_edge[dep] = 1;
    dfs_choose_edge(dep + 1, well_mask, well_sum, pipe_sum + edge_w[dep]);
    choose_edge[dep] = 0;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> well_cost[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cin >> pipe_cost[i][j];
    }

    // 建出全部水管边（只取上三角，跳过自环）
    edge_cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            edge_cnt++;
            edge_u[edge_cnt] = i;
            edge_v[edge_cnt] = j;
            edge_w[edge_cnt] = pipe_cost[i][j];
        }
    }

    best_cost = INF;  // 全部打井一定可行，所以答案一定有上界
    for (int well_mask = 0; well_mask < (1 << n); well_mask++) {
        ll well_sum = 0;
        for (int i = 1; i <= n; i++) {
            if ((well_mask >> (i - 1)) & 1) well_sum += well_cost[i];
        }
        if (well_sum >= best_cost) continue;  // 光打井就比当前答案贵，没戏
        for (int e = 1; e <= edge_cnt; e++) choose_edge[e] = 0;
        dfs_choose_edge(1, well_mask, well_sum, 0);
    }

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

复杂度

时间 $O\!\left(2^n \cdot 2^m \cdot (n+m)\right)$ ，空间 $O(n+m)$ 。 $n=5$ 时约 $3\times10^4$ 次检查， $n=6$ 时已经到 $2\times10^6$ ，只能算很小的数据。

瓶颈

这个暴力暴露了两件事：

决策被拆成两类，还带耦合。 "哪块田打井"和"哪两条田之间铺管"必须合在一起判断，单看任何一部分都定不了合法性，因此没法简单地分别贪心。
合法性检查在重复付账。 每检查一次方案就要重建一次连通块，而真正的信息其实只是"这些田是否被连成一片、并且整体有水"。这个信息本可以用更省的方式表达。

关键的问题是第二个：能不能把"有水"和"连通"合成同一个概念，让合法性判断变成"和某个固定点连通"？

正解

关键观察

回到"水从哪来"。铺管不产生水，只在田与田之间搬运水；打井才是水进入农场的位置。于是每块田最终都有一条供水链：从这块田出发，沿若干根已铺的水管走，最后落到某块打了井的田上，即

\text{田地} \;\longrightarrow\; \cdots \;\longrightarrow\; \text{打了井的田地}.

这条链的每一段都是我们为它付过一次钱的边：铺管付 $P_{ij}$ ，而"打了井"这一段……目前还只是田自己的属性，不是一条边。问题就出在这里：链的末端少了一条边。

补上它。想象农场外面有一处水源，记作虚拟点 $S$ ，在第 $i$ 块田打井，就等于从 $S$ 拉一条管子接到第 $i$ 块田，费用 $W_i$ 。于是：

$S \to i$ ，权 $W_i$ ：在第 $i$ 块田打井；
$i \to j$ ，权 $P_{ij}$ ：在 $i,j$ 之间铺一根水管。

这样"打井"和"铺管"变成了完全同一种东西——一条有权值的边，全部水都从 $S$ 流出。样例建成的图共 $4+6=10$ 条边：

text

1
2
3
4
5
6
7
8打井（虚拟源点 S 发出的边）
  S --1  权 5          S --2  权 4
  S --3  权 4          S --4  权 3

铺管（田与田之间的边）
  1--2 权 2   1--3 权 2   1--4 权 2
  2--3 权 3   2--4 权 3
  3--4 权 4

前者权值就是 $W_i$ ，后者权值就是 $P_{ij}$ 。在这个视角下，“所有田都有水"等价于" $S$ 与全部 $n$ 块田连通”：从 $S$ 沿边走到某块田的路径，正是那条供水链，路径上每一段都是付过钱的边。

思路

现在问题变成了一个纯图论问题：在 $n+1$ 个点、 $n+n(n-1)/2$ 条边的图上，选一个边集，让 $S$ 与全部田连通，且边权和最小。这正是最小生成树。下面把两个方向各自说清楚，确认这个转化没有丢信息。

方向一：任意合法方案都能看成连通结构。 给定合法方案（井集 $J$ 、管集 $E'$ ）。为每口井 $i \in J$ 加入边 $(S,i)$ ，为每根管 $(i,j)\in E'$ 加入边 $(i,j)$ 。任取一块田 $u$ ，按合法性它沿水管链 $u=v_0 \to v_1 \to \cdots \to v_k$ 追到某口井 $v_k \in J$ ；这条链在图中存在，再加上边 $(S,v_k)$ ，就知道 $u$ 与 $S$ 连通。全部田都这样，所以 $S$ 与所有田连通，且选中边权之和恰好等于方案花费。

方向二：任意生成树都能排出合法施工顺序。 给定 $n+1$ 点图的一棵生成树 $T$ 。把树中所有形如 $(S,i)$ 的边理解为"在 $i$ 打井"，其余树边理解为"铺这根水管"。树连通，所以从 $S$ 做 BFS 能到达每块田，且每块田在树上有唯一的父链通向 $S$ 。按 BFS 序施工：处理到 $u$ 时，若父边是 $(S,u)$ 就打井，否则父点已处理完（BFS 序保证），铺管 $(parent(u),u)$ 。整个过程不会出现"还没水就先铺管"，所以这是一个合法方案，花费等于树权。

两个方向都保持花费不变，因此"最小花费的合法方案"与"最小权生成树"的最优值相等。这里"总能排出施工顺序"靠的正是树的唯一父链：选哪些边和按什么顺序施工是同一件事。

为什么最优解一定无环。 在任意合法连通结构里，若有环，删掉环上任一条边：环上其余边仍把这圈点连在一起，所以连通性不变；而所有权值非负（ $W_i \geqslant 1$ ， $P_{ij}\geqslant 0$ ），删边后花费不增。反复删到无环，就得到点数相同的连通无环子图，即生成树。所以最优解总能取成树，最便宜的那棵就是 MST。

边界： $P_{ij}=0$ 。 本题的 $P_{ij}=0$ 表示"铺一根免费的水管"，是一根货真价实的 $0$ 权边，必须建进图里；把它当成"没有水管"丢掉就会算大。矩阵对角线上的 $P_{ii}=0$ 是自环，跳过。

边界：可能要多于一口井。 正因为有 $S$ ，模型不会隐含"只打一口井"的假设。例如两块田 $W_1=W_2=3$ 、 $P_{12}=1000$ 时，MST 会选 $(S,1)$ 与 $(S,2)$ 两条边，答案是 $6$ ——两口井；若 $P_{12}=0$ ，则 $3+0=3$ ，一口井加一根免费管。写暴力时若先入为主地固定"只在最便宜的田打井"，这两种情形会直接算错。

代码

用 Kruskal：把 $S\to i$ 的 $n$ 条边和田之间的 $\frac{n(n-1)}{2}$ 条边放进同一个边表，按权值排序，用并查集逐条尝试，两端不同块就选入。

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134/**
 * 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 10:20
 * update_at: 2026-10-21 10:20
 */
// P1550 [USACO08OCT] Watering Hole G
// 题意：第 i 块田可以花 W_i 打井，也可以花 P_ij 与第 j 块田铺一根水管；
//       求让所有田都有水（自己打井，或沿水管连到有水的田）的最小总花费。
//
// 建模：加一个虚拟水源点 S（编号 n + 1），表示"农场外面的那处水"。
//   S -- i   权 W_i    在第 i 块田打井，就是从这个水源接到第 i 块田
//   i -- j   权 P_ij   在两块田之间铺一根水管
// 这样"打井"和"铺管"都变成了同一种东西——一条边，于是
//   合法方案  <=>  S 与全部田连通的一张子图  <=>  一棵生成树
// 总花费就是选中边的权值和，问题变成在这个 n + 1 点图上求最小生成树。
//
// 注意 P_ij = 0 在本题是"免费水管"，是合法的 0 权边，必须建进图里；
// 只有 i == j 的对角线自环要跳过。
//
// 边数约 n^2/2 + n，n <= 300 时约 4.5 万条，用 Kruskal 排序后扫描即可。
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXN = 305;              // 田地数上限 n <= 300
ll well_cost[MAXN];                // well_cost[i]：在第 i 块田打一口井的花费 W_i
ll pipe_cost[MAXN][MAXN];          // pipe_cost[i][j]：第 i 块田与第 j 块田之间铺水管的花费 P_ij

// 一条无向边：从 u 连到 v，边权 w。点编号 1..n+1（n+1 是虚拟水源点 S）。
// 点编号要当数组下标用，写成 int；边权和最大约 3e7，但统一用 ll 更稳。
struct Edge {
    int u;  // 起点
    int v;  // 终点
    ll w;   // 边权
};

// 边权小的排在前面，Kruskal 每次都先试当前最小的边。
bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

// 找 x 所在集合的根，顺路把路径上的点直接挂到根上（路径压缩）。
int dsu_find(vector<int> &dsu_parent, int x) {
    if (dsu_parent[x] == x) return x;
    dsu_parent[x] = dsu_find(dsu_parent, dsu_parent[x]);
    return dsu_parent[x];
}

// 合并 a、b 所在的两个集合；两端本来就连通时返回 false。
// dsu_size[x] 是 x 当根时该集合的点数，用来按大小合并。
bool dsu_merge(vector<int> &dsu_parent, vector<int> &dsu_size, int a, int b) {
    int root_a = dsu_find(dsu_parent, a);
    int root_b = dsu_find(dsu_parent, b);
    if (root_a == root_b) return false;
    // 小集合接到大集合下面，配合路径压缩，单次操作接近常数。
    if (dsu_size[root_a] < dsu_size[root_b]) swap(root_a, root_b);
    dsu_parent[root_b] = root_a;
    dsu_size[root_a] += dsu_size[root_b];
    return true;
}

// 求最小生成树，按值接收边表，排序不会打乱调用者的边表顺序。
// 返回 true：图连通，answer 存 MST 的总权值；
// 返回 false：图不连通，没有生成树，answer 无意义。
bool kruskal(int node_cnt, vector<Edge> edges, ll &answer) {
    sort(edges.begin(), edges.end(), cmp_edge);

    // 并查集跟着点数开，放在函数里比固定大小的全局数组安全。
    vector<int> dsu_parent(node_cnt + 1);   // dsu_parent[x]：x 的父节点，x 是根时等于 x
    vector<int> dsu_size(node_cnt + 1, 1);  // dsu_size[x]：x 是根时该集合的点数
    for (int i = 1; i <= node_cnt; i++) dsu_parent[i] = i;

    answer = 0;
    int selected = 0;  // 已选边数，一棵生成树正好要 node_cnt - 1 条

    for (const Edge &edge : edges) {
        // 自环、两端已经连通的边都会成环，不能选。
        if (!dsu_merge(dsu_parent, dsu_size, edge.u, edge.v)) continue;
        answer += edge.w;
        selected++;
        if (selected == node_cnt - 1) break;
    }

    return selected == node_cnt - 1;
}

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

    int field_cnt;  // 田地数 n
    cin >> field_cnt;

    // 打井代价：每块田从水源接一条边
    for (int i = 1; i <= field_cnt; i++) {
        cin >> well_cost[i];
    }
    // 铺管代价矩阵
    for (int i = 1; i <= field_cnt; i++) {
        for (int j = 1; j <= field_cnt; j++) {
            cin >> pipe_cost[i][j];
        }
    }

    int source = field_cnt + 1;  // 虚拟水源点 S，表示"农场外面的那处水"
    vector<Edge> edges;
    edges.reserve(field_cnt * field_cnt + field_cnt);

    // S 到每块田：权 W_i，表示"在这块田打井"
    for (int i = 1; i <= field_cnt; i++) {
        edges.push_back({source, i, well_cost[i]});
    }

    // 田与田之间：只取上三角，矩阵对称不必重复建边
    for (int i = 1; i <= field_cnt; i++) {
        for (int j = 1; j <= field_cnt; j++) {
            if (i >= j) continue;  // 跳过对角线自环与下三角
            // P_ij = 0 是"免费水管"，是合法的 0 权边，绝不能像"无优惠"那样丢掉
            edges.push_back({i, j, pipe_cost[i][j]});
        }
    }

    ll answer = 0;
    // 每块田都有一条到 S 的边，这张图必然连通，返回值一定为 true
    kruskal(source, edges, answer);
    cout << answer << '\n';

    return 0;
}

边表里一共有 $n+\frac{n(n-1)}{2}$ 条边；因为每块田都有一条到 $S$ 的边，图必然连通，所以 Kruskal 一定能选满 $n$ 条边（ $n+1$ 个点的生成树共需 $n$ 条），函数返回值必然为 true，不需要处理不连通的情况。

同一套算法在 Python 下的写法与 C++ 逐行对应：读入用 next() 顺序消费，并查集用迭代路径压缩。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74#!/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 10:20
# update_at: 2026-10-21 10:20
#
# P1550 [USACO08OCT] Watering Hole G
# 建模：加虚拟水源点 S（编号 n + 1），
#   S -- i   权 W_i    在第 i 块田打井 = 从水源接一条边到这块田
#   i -- j   权 P_ij   两块田之间铺一根水管
# 合法方案等价于 S 与全部田连通，于是答案就是这 n + 1 个点的最小生成树。
# P_ij = 0 是免费水管，是合法的 0 权边，必须保留；只跳过 i == j 的对角线自环。

import sys

# 类型别名（Python 3.12+ 的 type 语句），相当于 C++ 的 using / typedef
type Edge = tuple[int, int, int]  # (起点 u, 终点 v, 边权 w)


def find(parent: list[int], x: int) -> int:
    """找 x 所在集合的根，顺路把路径上的点挂到根上（迭代压缩，不受递归深度限制）。"""
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:
        parent[x], x = root, parent[x]
    return root


def kruskal(node_cnt: int, edges: list[Edge]) -> int | None:
    """返回最小生成树总权值，图不连通时返回 None；sorted 生成新列表，不打乱调用者的边表。"""
    parent = list(range(node_cnt + 1))  # parent[x]：x 的父节点，x 是根时等于 x
    size = [1] * (node_cnt + 1)         # size[x]：x 是根时该集合的点数

    total = selected = 0
    for u, v, w in sorted(edges, key=lambda edge: edge[2]):  # 边权小的先试
        root_u, root_v = find(parent, u), find(parent, v)
        if root_u == root_v:  # 两端已经连通，选它就会成环
            continue
        if size[root_u] < size[root_v]:  # 小集合接到大集合下面
            root_u, root_v = root_v, root_u
        parent[root_v] = root_u
        size[root_u] += size[root_v]
        total += w
        selected += 1
        if selected == node_cnt - 1:  # 生成树正好 node_cnt - 1 条边，选满就停
            break
    return total if selected == node_cnt - 1 else None


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    field_cnt = next(data)     # 田地数 n
    source = field_cnt + 1     # 虚拟水源点 S，表示"农场外面的那处水"

    edges: list[Edge] = []
    # S 到每块田：权 W_i，表示在这块田打井
    for i in range(1, field_cnt + 1):
        edges.append((source, i, next(data)))

    # 田与田之间：矩阵对称，只取上三角；P_ij = 0 是免费水管，要保留
    for i in range(1, field_cnt + 1):
        for j in range(1, field_cnt + 1):
            price = next(data)
            if i < j:
                edges.append((i, j, price))

    # 每块田都有一条到 S 的边，图必然连通，返回值不会为 None
    print(kruskal(source, edges))


if __name__ == "__main__":
    solve()

复杂度

点数为 $n+1$ ，边数为 $O(n^2)$ 。Kruskal 的主开销是排序，时间 $O(n^2 \log n)$ ，并查集部分近似 $O(n^2\alpha(n))$ ，被排序掩盖；空间 $O(n^2)$ 存边表与费用矩阵。 $n=300$ 时边数约 $4.5\times10^4$ ，实测 C++ 单个测试点 $14$ ms、约 $3$ MB，Python 约 $44$ ms、约 $15$ MB。

验证记录

官方样例 in1：main.cpp、main.py、brute.cpp 均 AC，输出 9，与 out1 一致。

对拍用 gen.py 生成 300 组小数据（ $n \leqslant 5$ ，覆盖 $n=1$ 、 $W_i$ 极小、 $W_i$ 极大、 $P_{ij}$ 全 0、 $P_{ij}$ 远大于 $W_i$ ，其中 139 组含 $P_{ij}=0$ ），再用 brute.cpp 的输出作标准答案，分别评测主解：

提交	命令	结果
main.cpp	roj-local-judge-lite main.cpp --data-dir /tmp/stress1550	AC 300/300
main.py	roj-local-judge-lite main.py --data-dir /tmp/stress1550	AC 300/300

brute.cpp 与 main.cpp 不共享实现：暴力按定义枚举打井集合与铺管集合，正解走虚拟源点 + MST。另测 $n=300$ 随机极限数据（--time 2000 --memory 256）：C++ AC， $14$ ms / $3$ MB；Python AC， $44$ ms / $15$ MB。

总结

本题的难点不在最小生成树模板，而在把一个"两类决策、还带依赖关系"的建模问题变成纯粹的最小生成树：

虚拟源点为什么必要：铺管的每一段都是边，只有"打井"不是边，导致供水链的末端悬空。补上虚拟水源点 $S$ 、把打井建成 $S \to i$ 的边，所有水就有了统一的出处，合法性判断也从"每个连通块都有井"简化成"与 $S$ 连通"。
两个方向都要成立：合法方案沿供水链加 $(S,\cdot)$ 边即可得到连通结构；反过来树的唯一父链保证能按 BFS 序排出"先有水、后铺管"的施工顺序。两者花费一致，所以等价。
最优解无环：删环边连通性不变、花费不增，故最优解总能取成树。

一句话记法：把所有"凭空获得"的手段都接到同一个虚拟源点上，剩下的就是模板题。 顺带记住两个易错点—— $P_{ij}=0$ 是免费水管而非"没有水管"； $S$ 的存在允许最优解打多口井。