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容量31-3长度1容量12-4长度2容量23-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 能不能再快一点二分限重的优化思路有同学可能会问枚举每一条边的容量能不能改成二分答案这里要特别小心。二分法的前提是答案具有单调性而这道题里“容量门槛”和“最短距离”之间并不构成简单的单调关系。门槛提高可行的边减少最短距离可能变大也可能直接不可达。但答案要求的是“在所有可行路线中选择容量尽量大、距离尽量短的路线”这两个维度会互相制约。表面上看似乎可以二分容量但距离并不是容量的单调函数所以单纯二分容量的做法在本题里行不通至少没有枚举法来得直接和稳妥。下表对比一下各种思路思路复杂度能解决什么为什么没用/不够好直接DFS枚举路径O(n!)极小规模数据数据稍大就爆炸并查集按容量排序O(m log m)最大瓶颈路径不看距离无法处理第二关键字“最短距离”给定W跑一次最短路O(n^2 m)固定人数下的可行路线题目需要的是全局最优解枚举每条边容量最短路O(m(n^2m))瓶颈约束下的最短路本题解法二分容量最短路O(log m(n^2m))单调可行性判断本题答案不满足单调性容易错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数组初始化为-1cnt从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的初赛与其刷一大堆“看图写代码”的模板题不如多花点时间练习把应用题转成图论模型。比如看到“每条路有长度和承重限制”就想到“容量受限最短路”看到“每个点有等待时间”就想到“带权最短路”看到“只能走编号递增的点”就想到“有向无环图上的递推”。我带学生回炉这道“郊游活动”时通常只让他们干一件事不看答案先试着把主函数读懂用一句话复述出“这个程序在枚举什么、计算什么、比较什么”。能流畅说出这句话的人不填代码也能拿大部分分说不出这句话的人背再多模板也没用。这道题放在今天看依然是最好的图论思维练习题之一因为它教给你的不是一个模板而是一条完整的思考路径。
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容量31-3长度1容量12-4长度2容量23-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 能不能再快一点二分限重的优化思路有同学可能会问枚举每一条边的容量能不能改成二分答案这里要特别小心。二分法的前提是答案具有单调性而这道题里“容量门槛”和“最短距离”之间并不构成简单的单调关系。门槛提高可行的边减少最短距离可能变大也可能直接不可达。但答案要求的是“在所有可行路线中选择容量尽量大、距离尽量短的路线”这两个维度会互相制约。表面上看似乎可以二分容量但距离并不是容量的单调函数所以单纯二分容量的做法在本题里行不通至少没有枚举法来得直接和稳妥。下表对比一下各种思路思路复杂度能解决什么为什么没用/不够好直接DFS枚举路径O(n!)极小规模数据数据稍大就爆炸并查集按容量排序O(m log m)最大瓶颈路径不看距离无法处理第二关键字“最短距离”给定W跑一次最短路O(n^2 m)固定人数下的可行路线题目需要的是全局最优解枚举每条边容量最短路O(m(n^2m))瓶颈约束下的最短路本题解法二分容量最短路O(log m(n^2m))单调可行性判断本题答案不满足单调性容易错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数组初始化为-1cnt从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的初赛与其刷一大堆“看图写代码”的模板题不如多花点时间练习把应用题转成图论模型。比如看到“每条路有长度和承重限制”就想到“容量受限最短路”看到“每个点有等待时间”就想到“带权最短路”看到“只能走编号递增的点”就想到“有向无环图上的递推”。我带学生回炉这道“郊游活动”时通常只让他们干一件事不看答案先试着把主函数读懂用一句话复述出“这个程序在枚举什么、计算什么、比较什么”。能流畅说出这句话的人不填代码也能拿大部分分说不出这句话的人背再多模板也没用。这道题放在今天看依然是最好的图论思维练习题之一因为它教给你的不是一个模板而是一条完整的思考路径。
