企业官网建设流程全解析

1. 先弄明白这题在问什么，别被“郊游”两个字带偏

1.1 把“郊游活动”翻译成图论模型

NOIP 2016普及组初赛的完善程序题“郊游活动”，放到今天回看，仍然是我带学生复盘初赛时必讲的一道题。原因是它表面上是一道生活场景应用题，但本质上其实是一个很标准的“容量受限最短路”问题。

先按当年题面把条件列出来，方便后面展开。学校组织若干人去郊游，从地点1出发，要到达地点n，中间有一堆可供选择的路线。每条路线都有两个属性：一是长度，二是这条路上最多能同时通过的人数。由于是一个人多的队伍，所以整条路线能不能走，取决于这条路上所有路段中“最窄”的那一段能不能容纳整个队伍。换句话说，路径能通过的条件是：路径上所有边的容量都不小于队伍人数。

这下就清楚了，这个问题的实质是：给定一个无向图，每条边有长度和能力限制，要求找一条从1到n的路径，使得路径上所有边的容量都满足要求，并且路径总长度最小。

这就是一个典型的带有约束的最短路问题。很多同学当年第一眼看过去，会误以为它就是个普通最短路径，直接跑Dijkstra完事，结果填出来的程序逻辑完全不对，问题就出在根本没有把“容量约束”这件事放进去。

1.2 为什么不是“求一条最短路径”这么简单

如果只看距离，1到n的最短路可以直接用Dijkstra求，这没有争议。可一旦加上容量限制，事情就变了。举例来说，图里可能有一条距离很短的近道，但这条近道上有一座小桥，一次只能过1个人；而队伍有50人，这条路就算距离再短，也不能走。

所以这题不能只算距离，还要在选路的时候把容量条件考虑进去。也就是说，每一条边能不能被选进最短路径，需要一个额外的判定条件。这个条件不是看边的长度，而是看边能容纳的人数是否足够。

如果题目直接告诉你队伍人数是W，那逻辑很简单：跑一遍Dijkstra，只允许那些容量不小于W的边参与松弛，最后的dist[n]就是答案。但如果程序要求你在“所有可能的容量限制”下求一个最优解，那就要动用“枚举限重”的套路了。NOIP 2016初赛这道完善程序题，考察的正是后面这个东西。

1.3 一个能手动推的最小样例

为了后面讲代码时不至于悬空，我先给出一个能手动推完的微型样例。

假设有4个地点，4条双向路线：

• 1-2：长度2，容量3
• 1-3：长度1，容量1
• 2-4：长度2，容量2
• 3-4：长度1，容量2

现在队伍人数是2人。

如果只看距离，最短路径是1-3-4，总长度2。可是1-3这条路的容量只有1，根本走不了2个人的队伍。所以这条路线必须被排除。真正可行的路线是1-2-4，总长度4。

这个例子虽然小，但它把这类题的核心矛盾暴露得很彻底：最短的路线未必能走，能走的路线未必最短。所有算法设计都要围绕这件事来展开。

2. 为什么正解是“枚举限重 + 最短路”，而不是套模板

2.1 最朴素的思路：把每条边的容量都当一次“门槛”试一遍

既然队伍人数W决定了哪些边能走，哪些边不能走，那一个最直接的做法就是：把每条边的容量值挨个拿出来作为门槛，跑一遍最短路，然后记录下可行解中的最优答案。

为什么可以这么做？因为一条路径能不能走，取决于这条路径上容量最小的那条边。而全图容量最小的边，一定属于图中某条边。因此，所有可能的“瓶颈值”最多只有m种，也就是边的数量。我们把这m种瓶颈值全部枚举一遍，每一次都只允许容量不小于当前门槛的边参与最短路计算，那么最优路径一定会在某次枚举中被覆盖到。

这种做法在竞赛里叫“枚举限重 + 最短路”。它的复杂度是O(m * (n^2 + m))，当n不超过100、m不超过1000时，完全没问题。NOIP初赛的程序填空题给的数据范围一般也不会太大，所以这个算法是正解。

2.2 最短路部分为什么依然用Dijkstra

在门槛确定之后，问题就退化成了“在若干条合法边中求最短路”。这个子问题用Dijkstra解决就好。由于n很小，用朴素版Dijkstra其实就够了，甚至不需要堆优化。

很多人一看到最短路就条件反射地用Dijkstra+优先队列，这没错，但在这道题里需要理解一个关键点：Dijkstra的松弛操作是可以加条件的。我们做距离更新的时候，不是所有邻接边都去更新，而是只有满足e[j].cap >= limit的边才更新。这样得到的距离，就是在该容量门槛下的最短距离。

这也解释了为什么这道题能在完善程序里出现：它考的其实是你对Dijkstra模板的“微调能力”。模板会背没意义，你得知道哪些地方能改、哪些地方不能改。

2.3 能不能再快一点：二分限重的优化思路

有同学可能会问，枚举每一条边的容量，能不能改成二分答案？这里要特别小心。二分法的前提是答案具有单调性，而这道题里“容量门槛”和“最短距离”之间并不构成简单的单调关系。

门槛提高，可行的边减少，最短距离可能变大，也可能直接不可达。但答案要求的是“在所有可行路线中选择容量尽量大、距离尽量短的路线”，这两个维度会互相制约。表面上看，似乎可以二分容量，但距离并不是容量的单调函数，所以单纯二分容量的做法在本题里行不通，至少没有枚举法来得直接和稳妥。

下表对比一下各种思路：

2.4 为什么优先队列不是必须的

这道题如果放在C++里实现，n最大也就100上下，用朴素Dijkstra完全足够。每次找一个未访问且dist最小的点，O(n)扫描即可。用堆优化Dijkstra反而增加了代码量，也增加了完善程序中“填空”的复杂度。

我在实际教学里经常提醒学生：不要为了炫技去堆数据结构，初赛完善程序题考的永远是算法思路的清晰度，而不是代码的复杂程度。你能不能在50行以内把逻辑说清楚，比能不能写出一个高优化的堆版本重要得多。

3. 看着原题程序填空：四个关键位置与判定逻辑

3.1 预备动作：邻接表与数据结构的设置

我们按一种可复现的C++写法来还原程序。首先定义边结构体和链式前向星。

#include <bits/stdc++.h> using namespace std; const int N = 105; const int M = 1005; const int INF = 0x3f3f3f3f; struct Edge { int to, dist, cap; int next; } e[M * 2]; int head[N], cnt; int n, m;

这里head数组初始化为-1，cnt从0开始。链式前向星加边的时候，无向图必须把一条边当成两条有向边来加，否则后半部分的路线直接断掉。这个点看似简单，但我在带学生的过程中发现，很多人加边时只加了一次，导致后面跑最短路永远只能走出单向路径，数据一大就错得莫名其妙。

加边函数是这样：

void addEdge(int u, int v, int dist, int cap) { e[cnt].to = v; e[cnt].dist = dist; e[cnt].cap = cap; e[cnt].next = head[u]; head[u] = cnt++; }

主函数里要记得调用两次：

addEdge(u, v, dist, cap); addEdge(v, u, dist, cap);

完善程序考试中，这里常常会留一个空让你填边的总数上限，填2倍还是填m倍，就看题目怎么定义数组。见到无向边，第一反应就应该是两条。

3.2 check函数里最短路的主体

接下来是最核心的check(int limit)函数。这个函数的作用是：在“只允许容量不小于limit的边”的前提下，求从1到n的最短距离。

int d[N]; bool vis[N]; bool check(int limit) { memset(d, 0x3f, sizeof(d)); memset(vis, 0, sizeof(vis)); d[1] = 0; for (int i = 1; i <= n; ++i) { int u = -1; for (int v = 1; v <= n; ++v) { if (!vis[v] && (u == -1 || d[v] < d[u])) { u = v; } } if (u == -1 || d[u] == INF) break; vis[u] = true; for (int j = head[u]; j != -1; j = e[j].next) { int v = e[j].to; if (e[j].cap >= limit && d[v] > d[u] + e[j].dist) { d[v] = d[u] + e[j].dist; } } } return d[n] != INF; }

这里有几个关键位置，也是当年试卷上最常挖空的地方：

第一个，找最小未访问节点时，条件是!vis[v]，不能多也不能少。漏掉“未访问”这个条件，同一个点会被反复选中，等于Dijkstra白写了。

第二个，松弛条件里别忘了e[j].cap >= limit。这一句是整个算法的灵魂。没有它，Dijkstra就是在求普通最短路；加上它，才真正实现了容量的限制。很多同学当年就是在这里把大于号小于号写反，一会儿能走的路全不能走，一会儿不能走的路全放进来，整个答案离大谱。

第三个，返回条件d[n] != INF。这是判断在当前容量门槛下，从1到n是否还存在一条合法路径。如果d[n]是一个很大的数，说明这个限制下根本走不通，这个门槛不应该被拿去更新答案。

提示：在填代码时，如果看到memset(d, 0x3f, sizeof(d))，就要立刻反应过来，后面的比较都要拿INF作为不可达的判据，而不是拿0去判断。

3.3 主循环里枚举限重的写法

接下来就是主函数的框架：

int main() { memset(head, -1, sizeof(head)); cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v, dist, cap; cin >> u >> v >> dist >> cap; addEdge(u, v, dist, cap); addEdge(v, u, dist, cap); } int ans = INF; for (int i = 0; i < cnt; ++i) { int limit = e[i].cap; if (check(limit)) { ans = min(ans, d[n]); } } cout << ans << endl; return 0; }

这段代码的含义是：把每条边的容量单独拎出来当作一个门槛，跑一次check。如果这个门槛下存在可行路线，就把对应的最短距离拿去更新答案。

这里有一个很容易被忽略的细节：check(limit)跑完之后，d[n]会被写入这个限制下的最短距离。所以ans = min(ans, d[n])里的d[n]必须紧跟check之后使用，不能把其他地方的d[n]拿过来用。我在批改学生作业时经常看到有人把ans = min(ans, d[n])写在循环外面，结果答案永远是INF，代码风格上没什么问题，但逻辑已经跑偏了。

枚举完所有边之后，ans里存的就是所有可通行路线中距离最短的那条的长度。

3.4 输出答案与特殊情况的处理

输出时直接cout << ans即可。不过有一种情况需要额外想一下：如果图本身不连通，或者任何一条边的容量都不满足队伍要求，导致所有check都返回false，那么ans会一直是INF。

竞赛题的数据一般不会设计这种离谱的情况，但写代码时最好还是留个心眼。如果题目保证有解，那就无所谓；如果没保证，稳妥的写法是判断一下ans == INF并输出-1或题目要求的特殊值。完善程序题里一般不考这个分支，但它体现了一个程序员对边界情况的敏感度。

4. 从考场视角复盘，这道题的失分点都在哪

4.1 第一坑：松弛条件里的限重符号写反

这是我在各种场合反复强调的一个坑。松弛条件的中文意思是：只有这条边的容量足够大，才允许它参与最短路的更新。翻译成代码就是e[j].cap >= limit。

很多人在考场上一紧张，会把这个条件写成e[j].cap <= limit。这样一来，容量越小的边反而越容易被选中，完全反了。考场环境下不容易发现这个错误，因为样例数据小，可能凑巧也能跑出一个数字，但那个数字离正确答案差了十万八千里。

我给出的检查方法很简单：选一条容量最小但是距离最短的边，问自己一句“这条边到底该不该走”。如果答案是不该走，那你代码里的判断条件就应该是“容量大于等于门槛”，而不是“容量小于等于门槛”。

4.2 第二坑：无向边的对称性被忽略

如果题目换成有向图，加边加一次没毛病。但无向图里，从u能到v，从v也一定能到u。忽略这一点，最短路会在某个点突然断掉。

这个坑在第一轮学习时几乎人人都踩，没什么丢人的。关键是你要在代码里养成习惯：看到无向边，条件反射地加两次边。完善程序题如果在这里设置空位，通常不难填，但很多人会因为读题不仔细，以为题目给的路线是单向的，导致整个图结构都错了。

4.3 第三坑：INF取值和“不可达”判断

INF取0x3f3f3f3f是个好习惯，因为两个0x3f3f3f3f相加也不会溢出int。但很多同学做题时喜欢用1e9甚至INT_MAX。用INT_MAX时，一旦在松弛操作里做加法，INT_MAX + 1会直接溢出变成负数，后面的比较全乱套。

所以这道题里，如果看到memset(d, 0x3f, sizeof(d))，就安心用0x3f3f3f3f。判断不可达时，用d[n] == INF或者d[n] > INF / 2都是可以的。

4.4 第四坑：枚举范围选错导致答案偏大

主函数里的循环条件是for (int i = 0; i < cnt; ++i)，其中cnt是加入的所有边的总数。因为无向图每条路会生成两条边，所以cnt实际上等于2*m。如果你循环写成了i < m，那就只枚举了一半的边，容量门槛的覆盖范围少了一半，答案很容易偏大。

为什么少了一半就不行？因为最优路径的瓶颈边可能是某条边反向存储时的那一份，而你枚举的恰好是另一条边的容量，数值有可能不同。虽然每条无向边两条方向上的容量一样，存储的时候顺序不同，但如果只枚举一半，你可能漏掉了某个关键容量值。稳妥的做法永远是用存储边的实际数量cnt作为循环上界。

5. 这道题带给后来者的实战启发

5.1 一个被很多人忽略的通用模型：路径上的“短板”约束

“郊游活动”这道题本质上代表了一类更广泛的图论模型——路径上的瓶颈约束。很多竞赛题都有类似的特征：每条边除了长度，还有一个额外的限制属性，比如容量、高度、宽度、电量消耗，路径能否走通取决于整个路径上这个属性的最小值。

这类问题有一个通用的思考框架：先枚举瓶颈值，再在这个瓶颈值约束下跑最短路径。如果你能把这个框架内化成自己的思维习惯，以后看到任何“最短路径+额外限制”的题目，都不会慌。所谓“完善程序”，考的从来不是一道题本身，而是你有没有建立起一套从题目到算法的翻译系统。

5.2 对初赛备考的建议：完善程序不该靠背

我带学生备考初赛的时候，最反对的就是背代码。完善程序题的代码填空，看似在考语法和细节，实际上在考你对算法的整体把握。你只有先看懂了主函数，知道整个程序在“枚举什么、更新什么、输出什么”，才能真正把每个空填对。

建议做题顺序是这样的：先看main函数，搞清楚程序是干什么的；再回头看被调函数的框架，猜每个函数解决什么问题；最后才去细看每个空周围的上下文。具体到这道题，你只要先读懂主函数里“枚举容量 + 调用check + 更新答案”这个三层结构，后面所有空格就都变成了顺水推舟。

还有一个小技巧：看到head数组和next字段，第一反应是链式前向星；看到memset(d, 0x3f)，第一反应是最短路；看到无向边加边两次，第一反应是记得对称。这些“指纹”其实会帮你快速定位代码的功能，做题速度能快上不少。

5.3 从NOIP到CSP，这类考题的进化路径

这几年NOIP改名CSP之后，完善程序的考察风格也在变化，但“郊游活动”这种题型的考察内核并没有消失。现在的题目更喜欢把图论模型藏在一个生活场景里，让你先做一步翻译，再去写算法。考察重点从“会不会背模板”转向了“能不能从题面抽象出模型”。

所以如果你现在还在准备NOIP/CSP的初赛，与其刷一大堆“看图写代码”的模板题，不如多花点时间练习把应用题转成图论模型。比如看到“每条路有长度和承重限制”就想到“容量受限最短路”，看到“每个点有等待时间”就想到“带权最短路”，看到“只能走编号递增的点”就想到“有向无环图上的递推”。

我带学生回炉这道“郊游活动”时，通常只让他们干一件事：不看答案，先试着把主函数读懂，用一句话复述出“这个程序在枚举什么、计算什么、比较什么”。能流畅说出这句话的人，不填代码也能拿大部分分；说不出这句话的人，背再多模板也没用。这道题放在今天看，依然是最好的图论思维练习题之一，因为它教给你的不是一个模板，而是一条完整的思考路径。