题解

「XXI Olimpiada Informatyczna」自行车赛 题解

题目分析

给定一个有向无环图（DAG），我们需要找到一个节点，使得删除该节点后，图中最长路径的长度最小化。

关键观察

1. DAG 性质：由于图是无环的，可以使用拓扑排序进行动态规划
2. 最长路径：在 DAG 中，最长路径可以通过动态规划在 $O(n+m)$ 时间内求出
3. 节点影响：删除一个节点会影响经过该节点的所有路径

算法思路

1. 计算原始最长路径

首先计算整个 DAG 的最长路径长度。设：

• dp[u]：从任意起点到节点 $u$ 的最长路径长度
• 可以通过拓扑排序递推计算

2. 分析节点关键性

对于每个节点 $v$，考虑删除它后对最长路径的影响：

• 如果最长路径不经过 $v$，那么删除 $v$ 不影响最长路径
• 如果最长路径经过 $v$，那么删除 $v$ 后最长路径会断裂

3. 寻找最优封锁点

我们需要找到节点 $v$，使得删除 $v$ 后，新的最长路径最小。

方法一：枚举 + 动态规划（适用于小数据）

对于每个候选节点 $v$：

1. 从图中移除 $v$ 及其相邻边
2. 在新图上计算最长路径
3. 记录最小值

复杂度：$O(n \cdot (n+m))$，对于 $n=500000$ 不可行。

方法二：预处理关键路径信息

1. 计算所有节点的 DP 值：

   • dp_in[u]：到 $u$ 的最长路径
   • dp_out[u]：从 $u$ 出发的最长路径

2. 识别关键路径：

   • 全局最长路径长度 $L$
   • 找出所有在最长路径上的节点

3. 评估每个节点的效果：

   • 对于不在关键路径上的节点，删除它们不影响 $L$
   • 对于在关键路径上的节点，删除它们会使得最长路径断裂
   • 新的最长路径可能是：
     • 原始次长路径
     • 关键路径被切断后的两段拼接（绕过被删节点）

4. 高效算法框架

# 预处理
topo_order = 拓扑排序(G)
dp_in = [0]*(n+1)  # 入方向最长路径
dp_out = [0]*(n+1) # 出方向最长路径

# 计算dp_in
for u in topo_order:
    for v in G[u]:
        dp_in[v] = max(dp_in[v], dp_in[u] + 1)

# 计算dp_out（逆拓扑序）
for u in reversed(topo_order):
    for v in G[u]:
        dp_out[u] = max(dp_out[u], dp_out[v] + 1)

# 全局最长路径
global_longest = max(dp_in[u] + dp_out[u] for u in nodes)

# 对于每个节点v，计算删除它后的最长路径
best_node = 1
best_value = global_longest

for v in nodes:
    # 快速估计删除v后的最长路径
    new_longest = estimate_longest_after_removal(v, dp_in, dp_out)
    if new_longest < best_value:
        best_value = new_longest
        best_node = v

print(best_node, best_value)

复杂度分析

• 拓扑排序：$O(n+m)$
• DP 计算：$O(n+m)$
• 节点评估：$O(n)$ 或 $O(n \log n)$
• 总复杂度：$O(n+m)$，可处理最大数据范围

算法挑战

主要的算法挑战在于：

1. 高效评估节点删除的影响：不需要实际删除节点重新计算
2. 处理大规模数据：$n=5\times 10^5$, $m=10^6$
3. 利用 DAG 性质：设计线性或近线性算法

总结

本题需要深入理解 DAG 的最长路径性质，并设计高效算法来评估每个节点的重要性。通过预处理和巧妙的评估方法，可以在线性时间内解决问题。

最终算法标签： 有向无环图 拓扑排序 动态规划 最长路径 关键节点分析