企业官网建设流程全解析

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]都已被计算。两种实现方式：

1. 显式拓扑排序：使用Kahn算法逐步处理入度为0的顶点
2. 隐式拓扑序：直接按顶点编号顺序处理（本题特性）

3. 两种实现方案对比

3.1 方案一：拓扑排序过程中DP（Kahn算法）

void topoSort() { queue<int> 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 方案二：遍历已知拓扑序DP

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; } } }

3.3 两种方案对比分析

4. 三大优化技巧

4.1 路径记录优化

常规方法使用pre数组递归输出路径，可能栈溢出。优化方案：

void iterativeShowPath(int end) { stack<int> 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; vector<int> edge[N]; void topoDP() { queue<int> 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; vector<int> 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; } } } stack<int> 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() { queue<int> 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存储前驱：

vector<int> 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. 实战应用建议

1. 竞赛技巧：

   • 先画图理解题目结构
   • 确认图的拓扑性质
   • 小规模数据手工验证

2. 调试方法：

   • 打印中间状态（dp数组）
   • 验证路径正确性
   • 检查边界条件（单个顶点情况）

3. 性能考量：

   • V≤200时两种方案均可
   • V≥1e5时需要优化存图方式
   • 注意递归输出路径的栈深度限制