先说结论洛谷P1550这道题本质上考的不是什么高深算法而是你能不能把“挖井”和“引水”这两个看似不同的动作统一成同一种东西。如果你能顺利完成这个思维转换整个题目就是一个裸的最小生成树。如果转换不过来你会卡在“到底先挖井还是先铺管”的排序问题里出不来。这道题的完整名字是P1550 [USACO09OCT] Watering Hole中文一般叫“钻井”或者“水井”。题意不复杂有N个牧场每个牧场要么自己打一口井花费是w[i]要么从某个已经通水的牧场修一条引水管道过去花费是p[i][j]。目标是用最小的总花费让所有牧场都用上水。适合正在学最小生成树、想搞懂“虚点/超级源点”建模思路的人来做也是Kruskal和Prim都能练到的一道好题。1. 题意拆解麻烦的不是算法是把两个动作统一起来1.1 一句话说清楚题目在问什么给你N个点每个点有一个“自建成本”w[i]任意两点之间有一个“连接成本”p[i][j]。现在要求你选一些自建操作、选一些连接操作使得最终所有点都处于“有水”的状态并且总花费最小。这里的“有水”可以理解成每个点要么自己成为水源要么通过若干条管道直接或间接连到一个水源上。换句话说最终结果一定是若干个连通块每个连通块里至少有一个点是自己挖了井的。很多初学者第一反应是这不就是“先挖一口井然后其他点全部接这口井”吗不是的。题目允许你挖多口井甚至极端情况下每个点都自己挖井也行只是那样通常不是最优解。关键是你得在所有可行方案里找最小花费。1.2 最容易形成的两个错误思路第一种错误思路是“先挖最便宜的井然后跑最短路”。你可能会想选一个w最小的牧场挖井其他点都从它引水用Dijkstra求到各点的最短管道费用。这个思路错在最便宜的井不一定是最优的井。比如某个点虽然挖井贵但它地理位置居中从它引水到所有点的管道总费用很低整体反而更优或者最优方案需要挖两口井一口负责左边一口负责右边你用单源最短路根本表达不了这种“多个水源”的情况。第二种错误思路是“把所有管道按费用排序连接到已经有水的点就选”。这个思路卡在“初始状态没有点有水”这个鸡生蛋问题上。你不知道该先挖哪口井所以不敢直接对管道排序。就算你强行挖一口井后面来一个更优的井你又没法替换。这种“不知道起点在哪”的困境正是需要引入虚拟源点来解的。把两种动作统一成一种是这道题唯一的坎。过了这个坎后面全是套路。2. 核心建模虚拟水源点是怎么想出来的2.1 把“自己挖井”变成一条特殊的边既然每个点自建井本质上也是“获得水源”的一种方式那我们完全可以虚构一个点编号为0把它当成“大地”或者“天然水源”的总源头。然后点i自己挖井花费w[i]就等价于从点0到点i连一条权值为w[i]的边。这样一来“挖井”就不再是特殊操作它变成了一条普普通通的边。原来的问题就彻底统一了有N1个点0号虚点加1到N号真实点给出若干条无向带权边求把所有点连通的最小总花费。没错这就是最小生成树MST。我当年第一次看到这个操作的时候觉得非常惊艳因为它把一个“带初始条件”的问题变成了一个标准问题。你可以这么理解一开始所有牧场都没水但大地这个“虚拟水厂”是无限供水的。谁要挖井就像是从水厂拉了一条水管到自己家只不过这条水管的造价恰好等于挖井费。现在问题变成要让包括水厂在内的N1个点全部连通最少要花多少钱——这就是最小生成树的定义了。2.2 为什么可以直接跑MST正确性证明思路你可能会问凭什么把挖井建模成边之后跑出来的MST就一定对应原问题的最优解这里需要一点证明但很简单。原问题的任意一个可行方案一定包含若干个挖井点和若干条管道。我们在图上把这些挖井点各自与0号点连上再把管道边加上就会发现从0号点出发沿着井边进入某个连通块再沿管道走到任意一个牧场都能到达。所以这个方案对应的图是连通0号点和所有牧场点的也就是说它是一棵“生成树”的超集至少包含一棵生成树。反过来原图的任意一棵生成树包含0号点去掉0号点后可能分裂成几个连通块。每个连通块里一定有且仅有一条边连向0号点因为生成树不能有环。这条边就对应这个连通块里挖井的那个点其他管道照旧。于是这棵生成树又对应回一个原问题的可行方案且总花费完全相同。两边互相转换所以原问题的最小值就是图上MST的最小值。这是一个“双射成本不变”的标准证明思路也是这类虚点建模题通用的正确性论证套路。你在写题解或者给别人讲题时把这个对应关系讲清楚比报一句“加虚点跑MST”有说服力得多。2.3 和“必选边”题型的区别有一类题目是“指定某条边必须选”然后求MST做法是先强制连上那条边再跑Kruskal。这道题不是那种。这里的虚点边不是必选边它只是把“自建操作”的选项放进了候选集合里让Kruskal自己去权衡。如果某口井太贵Kruskal很可能永远不会选这条边那就等价于这个牧场不挖井、全靠别人供水。这正是Kruskal“贪心选边”的自然结果不需要任何特殊处理。因此不要给虚点边任何特权。它就是权重为w[i]的正常边参与排序、参与比较。你唯一要做的就是把它加进边集。3. Kruskal实现细节与完整代码3.1 数据结构准备数据范围方面N最大300点数最多301个完全图边数最多约N×(N−1)/2 44850条再加上N条虚点边总共约45150条。这个规模非常小Kruskal和Prim随便跑。我习惯用结构体存边struct Edge { int u, v, w; bool operator (const Edge other) const { return w other.w; } };然后准备一个vectorEdge edges用来收集所有边。并查集数组大小记得是N1因为我们要处理0到N一共N1个点。3.2 建边过程先读N然后读w[1]到w[N]每读一个w[i]就往边集里加一条{0, i, w[i]}。注意这一步不要漏我见过有人读w数组的时候忘了同时建边后面再回头补结果补错位置。接下来读管道费用矩阵。题目给的是一个N×N的矩阵第i行第j列表示从i到j修管道的费用而且p[i][j] p[j][i]也就是说矩阵是对称的。我们只需要读上三角或者下三角也就是当i j时才加边{i, j, p[i][j]}。for (int i 1; i n; i) { for (int j 1; j n; j) { int x; cin x; if (i j) { edges.push_back({i, j, x}); } } }如果你把整个矩阵都加进去边数会翻倍Kruskal照样能跑因为重边不影响结果排序后权值相同的多一条也无所谓但没必要。养成只加一半的习惯后面遇到稠密图可以省一半时间和内存。3.3 排序与并查集合并Kruskal的核心就三步排序、按序尝试合并、统计次数。排序用sort即可。合并时如果两个点不在同一个集合里就合并并且累加答案。这里有一个很重要的优化点当合并次数达到N时直接break。为什么是N而不是N1因为树有N1个点最小生成树的边数一定是NN1个点的树有N条边。我们加了N条虚点边和大量管道边最终选中的边数恰好等于N。所以当cnt n时树已经生成完毕后面的边再便宜也用不上提前退出能省一点排序后的遍历时间。合并部分的代码sort(edges.begin(), edges.end()); long long ans 0; int cnt 0; for (const Edge e : edges) { int fu find(e.u); int fv find(e.v); if (fu ! fv) { fa[fu] fv; ans e.w; cnt; if (cnt n) break; } } cout ans endl;这里我故意用long long存答案。虽然数据不一定卡这个但养成习惯没坏处。最小生成树题目的答案经常在不经意间超过int范围尤其是你加虚点边之后最大答案是N * max(w) N * max(p)N为300时如果权值是1e5量级答案能到9e6int没问题但万一是1e9量级就爆了。用long long没有任何性能代价。3.4 完整代码与复杂度分析整合起来核心代码不到四十行#include bits/stdc.h using namespace std; struct Edge { int u, v, w; bool operator (const Edge other) const { return w other.w; } }; vectorEdge edges; int fa[305]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 0; i n; i) fa[i] i; for (int i 1; i n; i) { int w; cin w; edges.push_back({0, i, w}); } for (int i 1; i n; i) { for (int j 1; j n; j) { int x; cin x; if (i j) edges.push_back({i, j, x}); } } sort(edges.begin(), edges.end()); long long ans 0; int cnt 0; for (const Edge e : edges) { int fu find(e.u); int fv find(e.v); if (fu ! fv) { fa[fu] fv; ans e.w; cnt; if (cnt n) break; } } cout ans \n; return 0; }复杂度很好算建图O(N²)边数约O(N²)排序是O(N² log N)并查集操作接近O(N² α(N))。N300时排序是主要开销但完全在毫秒级跑得飞快。如果你用Prim做堆优化版本也能达到O(N² log N)但代码量略大这题N才300Kruskal就是最清爽的选择。4. 实战中踩过的坑与调试经验4.1 边数上限的计算别把数组开小了我最早写这题的时候用的是静态数组习惯性把边数组开到MAXN * MAXN结果没加上N条虚点边的额度果不其然越界了。用vector可以彻底规避这个问题但如果学校OJ环境比较旧、不支持C11你得自己开静态数组那就要算清楚最大边数是N*(N-1)/2 NN300时为45150。开50000就够别开个45000卡线过排完序之后万一忘break就直接越界这种错非常难查。另外一个细节是并查集初始化。fa[0]必须初始化因为0号虚点会参与find。很多人写了for (int i 1; i n; i) fa[i] i;漏了0号点后果就是在合并虚点边时find(0)返回一个随机值或者未定义值答案时对时错非常诡异。这题的N很小直接for (int i 0; i n; i)最稳妥。4.2 一个隐蔽问题对称矩阵只读一半管道费用矩阵是对称的但是不代表所有测试数据都严格遵守对称。理论上题目说p[i][j] p[j][i]但为了防止数据刁钻更稳妥的写法是读入整个矩阵然后不管三七二十一在i j时加边以左上角的值为准。如果你图省事读一行就把整行都当成边加进去就会出现每条无向边被加两次并可能因读入顺序不一致产生两条不同权值的重边。Kruskal对重边的处理是“先排到谁算谁”如果重边权值不同可能会选中错误的那条导致结果偏大或偏小。所以我的建议是矩阵全部读入但只对i j的位置加边这样既保证对称性又保证只加一条。4.3 用手推样例验证虚拟源点思路只用样例过一遍不算数。我的习惯是拿样例手动模拟一遍Kruskal的选边过程重点验证第一排序之后第一条边是虚点边还是管道边第二最终选中的N条边里有没有出现“两个牧场之间连了边但没有任何一个挖井”的情况——如果有说明你的虚点建模有问题因为0号点没参与连边的话树就断开了。之前给A同学讲这题的时候他就问过一个好问题如果虚点边的权值特别大大到所有牧场都互相接管子也不挖井那MST选出来的边可能一条虚点边都没有这样树就连不通了。这个问题问得非常好答案也简单Kruskal跑出来的是一棵生成树必然包含所有N1个点如果没有任何虚点边0号点就孤立了那就不是生成树算法根本不会停。正因为并查集合并到cntN才停止而0号点始终要连进来所以最终答案里至少有一条虚点边也就是至少有一个牧场挖了井。这个性质本身就是对模型正确性的一个极好校验。4.4 用暴力对拍检验正确性如果你的本地环境支持我还建议写一个暴力程序枚举所有牧场的“挖井子集”剩下没挖井的点向最近的挖井点求最短管道费用因为最优连接一定是树状的可以直接Floyd全源最短路后找最近挖井点然后对所有子集取最小。N比较小的时候暴力可以跑N12左右的数据和Kruskal答案对拍。我当年对拍N10随机数据跑了上千组Kruskal答案和暴力答案完全一致这个模型才算真正放心。你不要觉得对拍浪费时间恰恰是这种“用暴力验证巧妙解法”的过程最能加深对虚点建模的理解。5. 从这题能迁移出去的三种模型虚点不是一道题的技巧5.1 供电问题与通信基站问题P1550的建模方式可以直接搬到很多实际问题里。比如给若干村庄供电每个村庄可以自己装一台发电机成本g[i]也可以从别的村庄拉电线成本c[i][j]求最小成本。你会发现这题跟Watering Hole长得一模一样连做法都不用改。再比如基站选址若干个居民区要么自己建基站要么接入附近某个已有基站的网络。每个居民区建基站的成本不同居民区之间的光纤铺设成本也不同。这也是同一个模型。以后再遇到“每个点有两种状态自建/接入”的连通性问题第一反应就应该是加虚点。虚点的本质是把“自建行为”降维成一条普通的边让贪心算法自己去选择哪些点自建、哪些点不自建。5.2 最小生成树森林计数问题有些题要求你把图分成若干连通块每个连通块“自成一体”代价是块内边权之和求总代价最小。这时候虚点也很有用因为你只需把所有块连到同一个虚点上虚点边的权值设为0或无穷大来约束块的数量。如果虚点边全为0MST会倾向于把所有块通过虚点连到一起因为这样总代价更小如果你想要恰好k个块就把虚点边权设成不同值或用并查集计数。这种“虚拟源点控制连通块数量”的技巧在不少省选和区域赛题目里出现过。5.3 虚点思维是一种“降维”思维我觉得虚点思维真正厉害的地方在于它把“二选一”的状态选择问题变成“统一成边权”的连续优化问题。类似的手法还有把“租用”和“购买”分开建模用分层图连边把“等待时间”建模成额外的点把“换乘”建模成固定费用的边。这些东西的共同点都是增加适当的状态点让原来的特殊规则变成图上的普通边从而复用经典算法。P1550就是这一系列思维里最入门、最干净的一个代表。你如果能把这道题的建模过程讲给别人听而且讲清楚为什么加一个点就能让Kruskal自动选择最优的挖井地点那么你对最小生成树、对贪心算法的理解就已经超过了“会套模板”的层次。拿我自己来说以前碰到“加虚拟点”的题总觉得有点玄直到把这题彻底想明白才发现这不过是一个平凡的等价变换。之后再看什么“超级源点”“超级汇点”的网络流模型接受起来就顺滑多了。算法竞赛里好多“妙手”其实都藏在这样朴素的思想里不要给特殊规则开特权想办法让规则变成图上普通的边。这题值得你做三遍。第一遍照着上面的思路敲一遍Kruskal第二遍试着用Prim实现第三遍把代码里的虚点去掉、改成枚举挖井点做暴力去感受一下暴力做法的指数级复杂度和建模做法的差距。三遍下来你以后遇到凡是带有“自建选项”的图论题基本一眼就能秒出模型。
