NOIP 1996 挖地雷题解拓扑排序与动态规划的 2 种实现与 3 处优化1. 问题背景与建模思路1996年NOIP提高组的挖地雷题目是图论与动态规划结合的经典案例。题目描述多个地窖通过单向通道连接形成网络每个地窖有不同数量的地雷。玩家需要选择一条路径使得沿途挖取的地雷总数最大。这个问题可以抽象为有向无环图DAG上的最长路径问题。具体建模方式每个地窖作为图中的一个顶点地窖之间的通道作为有向边地窖中的地雷数量作为顶点权重关键性质题目说明编号小的地窖只能通向编号大的地窖这保证了图的拓扑序就是顶点编号顺序也确保了图中无环。2. 核心算法原理2.1 动态规划状态设计定义状态dp[i]表示以顶点i为终点的所有路径中点权加和最大的路径值。状态转移方程为dp[i] max(dp[j] a[i]) ∀j→i存在边其中a[i]表示顶点i的地雷数量。2.2 拓扑排序的作用拓扑排序保证了状态转移的无后效性——计算dp[i]时所有可能转移到i的顶点j的dp[j]都已被计算。两种实现方式显式拓扑排序使用Kahn算法逐步处理入度为0的顶点隐式拓扑序直接按顶点编号顺序处理本题特性3. 两种实现方案对比3.1 方案一拓扑排序过程中DPKahn算法void topoSort() { queueint q; for(int i 1; i n; i) if(deg[i] 0) { q.push(i); dp[i] a[i]; // 初始化 } while(!q.empty()) { int u q.front(); q.pop(); for(int v : edge[u]) { if(dp[v] dp[u] a[v]) { // 状态转移 dp[v] dp[u] a[v]; pre[v] u; // 记录路径 } if(--deg[v] 0) q.push(v); } } }3.2 方案二遍历已知拓扑序DPfor(int u 1; u n; u) { for(int v : edge[u]) { if(dp[v] dp[u] a[v]) { dp[v] dp[u] a[v]; path[v] u; } } }3.3 两种方案对比分析特性拓扑排序中DP遍历拓扑序DP时间复杂度O(VE)O(VE)空间复杂度O(VE)O(VE)代码复杂度较高较低适用性通用DAG已知拓扑序路径记录需要额外处理直接记录4. 三大优化技巧4.1 路径记录优化常规方法使用pre数组递归输出路径可能栈溢出。优化方案void iterativeShowPath(int end) { stackint s; while(end ! 0) { s.push(end); end pre[end]; } while(!s.empty()) { cout s.top(); s.pop(); if(!s.empty()) cout -; } }4.2 边界处理优化初始化时直接将所有dp[i]设为a[i]避免特殊处理孤立顶点for(int i 1; i n; i) { dp[i] a[i]; // 初始化为自身地雷数 if(dp[i] dp[mxi]) mxi i; // 顺便找最大值 }4.3 输入处理优化针对不同OJ的输入格式统一处理逻辑while(cin x y !(x 0 y 0)) { edge[x].push_back(y); deg[y]; }5. 完整代码实现5.1 拓扑排序DP完整代码#include bits/stdc.h using namespace std; const int N 205; int n, a[N], dp[N], deg[N], pre[N], mxi; vectorint edge[N]; void topoDP() { queueint q; for(int i 1; i n; i) if(deg[i] 0) q.push(i); while(!q.empty()) { int u q.front(); q.pop(); for(int v : edge[u]) { if(dp[v] dp[u] a[v]) { dp[v] dp[u] a[v]; pre[v] u; if(dp[v] dp[mxi]) mxi v; } if(--deg[v] 0) q.push(v); } } } void printPath(int v) { if(pre[v] ! 0) printPath(pre[v]); cout (pre[v] ? - : ) v; } int main() { cin n; for(int i 1; i n; i) { cin a[i]; dp[i] a[i]; if(dp[i] dp[mxi]) mxi i; } int x, y; while(cin x y x y) { edge[x].push_back(y); deg[y]; } topoDP(); printPath(mxi); cout endl dp[mxi]; return 0; }5.2 遍历拓扑序DP完整代码#include bits/stdc.h using namespace std; const int N 205; int n, a[N], dp[N], path[N], mxi; vectorint edge[N]; int main() { cin n; for(int i 1; i n; i) { cin a[i]; dp[i] a[i]; if(dp[i] dp[mxi]) mxi i; } int x, y; while(cin x y x y) edge[x].push_back(y); for(int u 1; u n; u) { for(int v : edge[u]) { if(dp[v] dp[u] a[v]) { dp[v] dp[u] a[v]; path[v] u; if(dp[v] dp[mxi]) mxi v; } } } stackint st; for(int i mxi; i ! 0; i path[i]) st.push(i); while(!st.empty()) { cout st.top(); st.pop(); cout (st.empty() ? \n : -); } cout dp[mxi]; return 0; }6. 算法扩展与变式6.1 处理带环情况如果图中可能存在环需要先检测环的存在bool hasCycle() { queueint q; int cnt 0; for(int i 1; i n; i) if(deg[i] 0) q.push(i); while(!q.empty()) { int u q.front(); q.pop(); cnt; for(int v : edge[u]) if(--deg[v] 0) q.push(v); } return cnt ! n; }6.2 多路径记录如果需要记录所有最优路径可以改用vector存储前驱vectorint pre[N]; if(dp[v] dp[u] a[v]) { dp[v] dp[u] a[v]; pre[v].clear(); pre[v].push_back(u); } else if(dp[v] dp[u] a[v]) { pre[v].push_back(u); }6.3 空间优化对于大规模图可以使用链式前向星存图struct Edge { int to, next; } edge[M]; int head[N], tot; void addEdge(int u, int v) { edge[tot].to v; edge[tot].next head[u]; head[u] tot; }7. 实战应用建议竞赛技巧先画图理解题目结构确认图的拓扑性质小规模数据手工验证调试方法打印中间状态dp数组验证路径正确性检查边界条件单个顶点情况性能考量V≤200时两种方案均可V≥1e5时需要优化存图方式注意递归输出路径的栈深度限制