最近刷UVa时撞上13116这道Multistory Labyrinth第一眼以为就是个走迷宫BFS莽一下就行结果仔细读完题发现完全不是那么回事。这道题把“楼层”这个概念实打实嵌进了网格迷宫模型里层与层之间靠传送点衔接整张图带权还可能带负分。这段时间我把这道题从建模到DP重头到尾撸了一遍踩了不少坑也整理出了一套能直接照抄的解法思路。如果你也在做图论DP、DAG最长路这类练习或者正在刷UVa题库这篇文章应该能帮你少走几条弯路。1. 题意拆解与核心考点1.1 多楼层迷宫在题目里到底是个什么结构先从题目结构说起。Multistory Labyrinth不是普通的二维迷宫它是一个由多层平面网格堆叠起来的立体结构每一层都是一张独立的网格图。你从某一层的某个格子出发可以沿着上下左右四个方向在当前楼层内移动也可以踩上某些特殊格子通过这些传送点直接跳到其他楼层去。每到达一个新格子就会获得或者失去该格子上标注的分数最终目标是到达指定的终点格子并让总得分尽可能大。这里要注意楼层不是孤立的。传送点把层与层连接起来整张地图变成了一张由跨层边和同层边构成的带权图。网格本身是节点每一步移动则相当于一条边。因为移动是带收益的所以这不是一个单纯求最短路径的问题而是一个求最大累计收益的问题。这类题最大的迷惑性在于看起来像迷宫实际上考的是图论建模和动态规划。如果你一上来就写BFS或者DFS搜索所有路径在数据范围稍微大一点的情况下会直接炸掉因为路径数量是组合级的暴力枚举根本撑不住。1.2 为什么一眼看出这是DAG最长路判断一道题能不能用DAG上的DP来解关键看图里有没有环。我在读题的时候重点确认的就是这一点跨层传送方向是不是单向的。把楼层按顺序编号为0到L-1如果传送方向只能从编号小的楼层去编号更大的楼层或者反过来那么任意一条路径从整体趋势上看一定是逐层推进的不可能出现绕了一圈又回到同一楼层同一格子的情况。而同层内移动虽然看起来是来回走动的但如果你把时间顺序算进去路径一旦通过传送门上升或下降一层就不可能再回到之前的楼层——除非存在反向跨层边那就另当别论了。这道题的前提恰恰就是传送方向单向且楼层逐级推进。因此整个图天然无环是一个标准的有向无环图。在DAG上求带权最长路不需要Dijkstra不需要SPFA直接用动态规划扫一遍就能出答案复杂度是线性的。这也是整个解法的核心突破口。1.3 与经典网格题的本质区别以前我们做的网格题比如求最短步数、求可达性、求方案数大多是在无权图上跑的BFS一把梭就完事。但Multistory Labyrinth这一类题引入了“边权”的概念而且权值有正有负。带权图上的最优路径问题就需要分情况讨论了。如果所有边权非负Dijkstra可以处理如果图里可能有负权边但无负环SPFA能用但最坏情况复杂度很难看如果图本身是DAG那就什么都不用纠结记忆化搜索或者拓扑序DP是最优解连优先队列都不用。这道题恰好落在第三种情况里所以我选DP方案而不是其他方法不是因为它简单而是因为它在数学上最契合问题结构。后面我会详细拆解完整的建图方式和两个可选的实现版本。2. 建模方案把迷宫变成一张带权DAG2.1 节点编号的心法要把二维网格叠成三维图第一步是编号。编号方案直接决定后面所有代码好不好写我推荐用一维编号。假设每层有R行C列共R乘C个格子。楼层编号floor从0到L-1行号r从0到R-1列号c从0到C-1。那么每个格子的全局编号可以设计为int id(int floor, int r, int c) { return floor * (R * C) r * C c; }这样设计的好处在于楼层越高编号区间越大。0层的格子编号是0到R乘C减11层的格子从R乘C开始依此类推。后面做拓扑排序或者记忆化搜索时我们能很方便地从节点编号直接倒推出它属于哪一层、哪一行哪一列不必单独维护坐标映射。我建议顺手再写一个反向解析函数调试时打印节点信息会非常方便int getFloor(int id) { return id / (R * C); } int getRow(int id) { return (id % (R * C)) / C; } int getCol(int id) { return id % C; }这个编号方案还有一个隐藏好处如果题目要输出路径我们只用一个数组存前驱节点的编号最后就能倒推出完整路径连结构体都不用定义。2.2 楼层内部的边权怎么定楼层内部的移动规则相对简单从当前格子走到上下左右相邻的格子如果目标格没越界就可以走。每进入一个格子背包里的分数就加上该格子的分值所以边的“代价”本质上就是目标格子的分值。这里有一个特别容易搞混的约定问题起点格子的分数要不要计入总得分。我在实践里习惯按“进入一个格子即获得该格子的分值起点不计算终点计算”来建模。如果题目待确认就老老实实把答案加减一个起点分值来对应不同约定。看清楚题目给出的样例和说明因为很多WA都是一开始约定没对齐导致的。楼层内的建边代码如下int dr[4] {-1, 1, 0, 0}; int dc[4] {0, 0, -1, 1}; for (int f 0; f L; f) { for (int r 0; r R; r) { for (int c 0; c C; c) { int u id(f, r, c); for (int k 0; k 4; k) { int nr r dr[k], nc c dc[k]; if (nr 0 || nr R || nc 0 || nc C) continue; int v id(f, nr, nc); g[u].push_back({v, score[f][nr][nc]}); } } } }注意这里我只建了出边没建反向边。对于求最长路来说正向边方向就是路径移动方向反向边是给输出路径用的后面单独说。2.3 跨层传送门的边权处理跨层传送是整个题目的题眼也是最容易出错的地方。传送门通常出现在特定层级的特定格子踩上去之后会瞬时传送到另一层楼的某个固定格子。传送的目的是跨越空间所以这条边的“收益”按题目表述处理可能是目标格子的分值也可能另有单独设定。我在本文约定它等于目标格的分值因为这是最常见也最合逻辑的一种设定。建边逻辑是当遍历到格子f, r, c时如果它对应着一组传送规则就把这一组规则解析出来找到目标楼层tf、目标行tr、目标列tc然后给编号u的节点添加一条有向边到编号v id(tf, tr, tc)的节点边权为score[tf][tr][tc]。值得多想一步的是传送门的存储方式。UVa题目输入一般会给很多组“传送点”描述如果你在建模循环时每次都遍历一遍传送表数据一多就会慢很多。我的做法是先建一个三维数组portal[L][R][C]值为-1表示没有传送门如果有传送目标就存一个targetId。这样在建图时只需要O(1)查询整体复杂度还是O(L乘R乘C)。还有一个小细节传送方向是从本层传到目标层。虽然大多数情况下都是往下层传但写代码时不要写死方向判断直接把解析出来的目标节点当作普通节点建边就好。万一题目存在“从低层传向高层”的传送门只要整张图没有成环DP依然成立如果成环了题目性质就变了后面我会专门讲。2.4 用一个不超过三层的微型迷宫手工推一遍光说理论容易飘我拿一个极小的例子快速过一遍建图逻辑。假设有2层每层是2乘2的网格每格分值随手填一下0层A(1) B(2) / C(3) D(4) 1层E(5) F(6) / G(7) H(8)再假设0层的C格是一个传送门能传到1层的E格。建图之后大概是这样0层内部A可以到B和CB可以到A和DC可以到A、D以及跨层到ED可以到B和C。1层内部E到F和GF到E和HG到E和HH到F和G。跨层边把节点C指向节点E边权为E的分值5。从A出发如果目标是H一条路径是A - C得3分- E得5分- G得7分- H得8分总得分是23分。另一条路径在0层绕一下可能有不同的分数组合。这已经可以看出模型的意义我们根本不用关心迷宫图形的样子只要把图建出来剩下的问题就是求最长路。3. 求解算法DAG最长路DP实战3.1 建好图后为什么不能直接BFS或Dijkstra边权有正有负这是关键。BFS要求所有边权相同最短路径才成立Dijkstra要求非负权因为它的贪心前提是“当前距离最小的节点未来不可能被更小的距离更新”负权会把这个前提打破。你拿Dijkstra去跑带负权的图常常会得到次优解而且样例还不一定能测出来非常坑。那SPFA行不行技术上可行但没必要。SPFA虽然能处理负权边但最坏情况下复杂度会退化到O(VE)在L、R、C都拉满的题目上很容易超时。DAG最长路能用线性DP解决你不会想用SPFA把可以线性解决的问题写成二次复杂度。记忆化搜索和拓扑排序DP本质都是利用“节点之间存在偏序关系”这个性质让每个节点只被计算一次从而把指数级的搜索空间压到O(NE)。这就是DAG动态规划的核心竞争力。3.2 版本一记忆化DFS实现定义dp[u]表示从节点u出发走到终点能得到的最优分数。注意这里的状态含义是“从当前节点出发”所以递归边界很自然如果u已经是终点直接返回该节点的分值否则枚举u的所有出边计算进入下一个节点v之后的最佳分数再加上跨过去那条边的收益取最大值。伪代码如下const int NEG -1e9; int dp[MAXN]; bool vis[MAXN]; int dfs(int u) { if (u target) return scoreAt(u); if (vis[u]) return dp[u]; vis[u] true; dp[u] NEG; for (Edge e : g[u]) { dp[u] max(dp[u], e.w dfs(e.to)); } return dp[u]; }这里有几个点需要细节处理。终点节点会优先返回自身分值而不是试图往外走这个逻辑必须放在枚举出边之前否则终点有出边时会被继续递归绕出环来就全乱了。另外如果某个节点根本走不到终点dp[u]会一直是NEG调用方需要判断这个状态是否合法。递归深度是一个隐患。多楼层迷宫节点总数可能达到几十万甚至上百万DFS的递归深度取决于拓扑链长度当链路很长时默认系统栈可能会爆。我实际测试过这一题如果在本地编译器里跑一般还比较稳但提交到UVa的在线评测环境不一定给你开足够的栈空间。所以更保险的版本是写成非递归的拓扑排序DP这也是我实战里更常用的方案。3.3 版本二拓扑排序迭代DP如果图天然按楼层编号有序而且所有跨层边都是从低层到高层那么节点编号本身就可以当拓扑序用。这种情况下你甚至不需要建拓扑序数组直接按楼层从高到低或者从低到高遍历一遍就行。更通用的写法是建图之后用一个入度数组做标准的Kahn拓扑排序得到拓扑序列。然后在拓扑序的逆序上做DP因为拓扑序里的方向是从前向后而dp[u]依赖u的后续节点v所以得从后往前推。代码如下vectorint topo; queueint q; int indeg[MAXN]; for (int i 0; i N; i) for (Edge e : g[i]) indeg[e.to]; for (int i 0; i N; i) if (indeg[i] 0) q.push(i); while (!q.empty()) { int u q.front(); q.pop(); topo.push_back(u); for (Edge e : g[u]) if (--indeg[e.to] 0) q.push(e.to); }需要注意拓扑排序的前提是有向无环。如果图中存在环Kahn算法会输出少于N的节点数这就是一个很好的判环信号。拿到拓扑序之后DP就可以写了。dp[v]表示从终点到v的最优值换个角度定义也无妨关键是状态转移要一致。vectorint best(N, NEG); best[target] scoreAt(target); for (int i (int)topo.size() - 1; i 0; i--) { int u topo[i]; if (best[u] NEG) continue; for (Edge e : g[u]) { best[e.to] max(best[e.to], best[u] e.w); } }这个写法的好处是没有系统栈风险而且你可以在得到dp的过程中顺便记录前驱节点一举两得。相比记忆化搜索我觉得迭代DP在竞赛环境里更“皮实”。如果题目中的楼层顺序天然可做拓扑序也可以省去Kahn排序直接先用一个数组标记传送方向保证无环然后按楼层降序遍历比Kahn少一倍的常数时间。3.4 输出完整路径是加分项题目不一定要求输出路径但调试过程中输出路径几乎是必需的。我的办法是维护一个pre数组对应该节点上一步走的哪个前驱节点。在逆序DP推进时一旦发现best[e.to]被更新就直接记录pre[e.to] u;最后从起点开始沿着pre跳直到终点就能还原完整路径。这里要注意起点和终点是否预先定义如果起点无法到达终点pre链会在某个环节断掉输出前需要判断。输出路径时我还踩过一个坑如果更新发生在等号右边也就是出现多个相同最优路径时题目没有特殊要求任选一条即可但如果你用了“大于就更新”遇到并列情况就会保留第一次找到的路径行为稳定可复现调试起来舒服得多。4. 避坑指南与调试实录4.1 起点分数到底计不计这是我在群里看到问得最多的问题之一。不同题目对“走到某格得到分数”的起点处理可能不同。这道题我的建模约定是起点不算分每移动到下一个格子时把目标格子的分值累加。但如果你是按“经过每个格子都计分包括起点”来写的答案所有的路径表达式里会统一多一个起点分数差一个常数。提交WA的时候先检查自己起点处理与题意是否一致别急着怀疑算法。我自己调试时用过一招把起点到终点的几步路径全部打印出来手动按约定算一遍总分和程序输出比对不一致就说明某个边权或者起点计数逻辑出了问题。4.2 传送成环导致的隐性Bug虽然题目保证无环但建模过程中很容易意外引入环。比如同层移动本身就是双向边如果跨层传送门是双向的楼层的先决条件就会被破坏。又比如传送门不小心把自己传回原楼层如果目标格子又连着别的传送门很容易形成大环。即使题目说保证无环我也建议建完图之后跑一次拓扑排序检查节点数量是不是等于N。不是的话立刻回头查传送门输入解析有没有理解偏。这个检查只有O(NE)的开销却能防住最伤脑筋的隐性WA。4.3 输入格式和EOF处理的坑UVa的输入风格非常统一多组case、空洞行、EOF结束。我处理多楼层迷宫输入时踩过的实际问题包括每层网格数据之间可能有空格也可能没有空行传送描述每个case都有不同的条数case结束以后不一定有明确的结束标记。推荐的稳定读法是逐行用函数读入然后逐段解析不假设某一行必然存在。传送门解析时如果用cin流读记得每一轮case开始时把所有全局数组重新初始化特别是edge容器用vector声明的要clear不然上一个case的边会残留到下一个case。我吃到过最痛的一次亏是传入数组用静态数组但忘记重置size结果导致下一组case在遍历时越界访问本地环境没炸交上去就RE。后来我养成了每次case开始先自查所有动态结构清空的习惯。4.4 负权边和INF设置的方案DAG最长路里如果所有边权都是正的初始化负无穷大和初始化0的区别不大但一旦出现负分格子节点间的路径可能因为额外绕路而变差dp的初始值就不能设成0必须设成一个足够小的数。用INT_MIN直接做初始值有风险因为你在做加法时可能溢出Int范围。更稳的做法是用一个自定义常量比如const int NEG -1e9;。如果节点数和边权的绝对值加起来也不会超过1e9这个值就足够安全。这个细节平时写题不觉得一旦遇到负数极端数据就特别能凸显问题。4.5 常见错误速查表我在实战排查时给自己整理过一张速查表横纵对照一下就能快速定位问题类型。症状可能原因检查方向样例过但提交WA起点分数计入规则不一致重新确认题意输出答案明显偏大图中存在环且DP朝错误方向传播跑拓扑排序判环答案整体偏小dp初始值没设成负无穷检查NEG常量答案永远一样传送门边权漏了或者目标格分值没加打印部分路径细节本地跑得动、OJ上RE静态数组大小或递归爆栈检查数组边界、改用迭代DP多个case之间互相污染全局数组未清空或vector未clearcase开始前统一reset这张表不能保证一次解决所有问题但每次调试前过一遍能帮你省下很多重复试错的时间。5. 跨层迷宫类题目的扩展思路5.1 如果传送门双向或者同层解法怎么变跨层传送门一旦变成双向的图里就可能出现环。带着正环的图里最长路没有保守答案因为你可以在环上反复转圈把分数刷到无限大。这时候DP就不再适用。处理办法通常是问自己题目的本意是不是“最多经过一个传送环”或者有步数限制否则就要考虑缩点或者换算法思路。如果只是存在负环最长路的说法也会变得很微妙。竞赛题很少在这种情况下让你裸跑SPFA求最长路而是会给一些额外的约束。遇到这种题目先别急着套模板看清楚限制条件再动手。5.2 多楼层思想的通用价值Multistory Labyrinth这题解答完我最大的感受是它的骨架可以套用到很多问题里。一个在二维网格上不好处理的问题通过增加“楼层”这一维度变成三维再用“单向传送”构造出天然的拓扑顺序最后统一转化为DAG上的DP——这是一条非常常见且实用的出题套路。如果你后续遇到类似的“层次图最短/长路”“分层状态DP”问题比如图论里的分层图最短路、状态机DP、带瞬移节点的BFS核心思路都是一模一样的。先把空间展开成多层再把层间转移建模为边问题就从图论变成了动态规划。我曾经拿这道题的代码框架去改一个“带飞行道具的网格寻宝题”只改了边的生成逻辑和状态含义整体结构几乎没动最后很快AC。这就是建模抽象带来的复用价值。5.3 对图论建模的心得做这类题最忌讳的就是拿到题目就开始写循环。先花五分钟在纸上把“节点是什么、边有哪些、权怎么算、会不会有环”这四件事想清楚后面写代码速度快得多调错的时间也少得多。这道题让我更深刻地体会到建模能力才是算法竞赛里最核心的能力数据结构和算法都是为建模服务的工具。如果你现在刚入门图论DP不妨找一个小的数据规模用例手动画出节点和边然后用程序打印出每个节点的dp值对照着理解一遍状态转移。这个过程可能有点费时间但效果比直接刷几十道题都好。5.4 后续可以继续练的同类题UVa里还有不少类似的题可以拿来巩固这套思路比如带层次图最短路的题目、带时间维度的状态DP、带特殊传送点的BFS问题。刷题要有意识地找共同点别贪多贪快。把一个模型吃透以后换个场景再遇到时你大概一眼就能认出它的本质。我个人比较推荐的做法是做完13116之后再找两到三题类似结构的题用同一套代码框架去改体会哪些地方是变体、哪些地方是不变的核心。这样比反复刷同类型模板题有效得多。写在最后UVa 13116 Multistory Labyrinth这道题表面是迷宫内里是DAG最长路中间隔着一层建模的窗户纸。捅破这层纸之后你会发现它并不难难的是在考场或者比赛状态下冷静地完成建图、定权、判环这一整套动作。建议你把我上面那段代码自己敲一遍跑过样例再试试不打印路径的情况下能不能一遍写对。这种手感只能靠实操磨出来光看题解记不住太久。我自己的经验是把这题啃透以后再遇到层状图相关的题目思路会顺畅非常多。