题目解析

问题理解

这是一个图论中的路径优化问题，需要找到从起点（1号路由器）到终点（n号路由器）的一条路径，使得：

1. 信号强度（初始为1）经过路径上所有放大器的乘积放大后达到最大值
2. 路径上每个节点的信号强度都不能超过该路由器的流量限制
3. 可以重复经过节点和边

代码算法分析

核心思路

代码采用了双向状态传播 + 动态规划的方法：

1. 正向传播：从起点1号路由器开始，计算从起点到达每个路由器时可能的信号强度

   • 使用二维数组f[i][j]记录从起点到路由器i时信号强度为j是否可达
   • 采用BFS方式传播状态，考虑所有可能的放大器路径

2. 反向传播：从终点n号路由器开始，计算从每个路由器到终点时允许的最大信号强度

   • 使用二维数组g[i][j]记录从路由器i到终点时信号强度为j时的最大允许值
   • 考虑路由器的流量限制和放大器系数

3. 结果计算：枚举所有放大器和状态组合，找到最大的合法信号强度

   • 对于每条放大器边(a→b,w)，结合正向传播到a的状态和反向传播从b开始的状态
   • 计算可能的最大信号强度：f[a][x] * w * g[b][j]

关键优化

• 状态范围限制：设置状态上限s = sqrt(1e9) + 1，将大范围问题分解为可管理的小范围问题
• 双向搜索：通过正向和反向传播，避免单一路径搜索的状态爆炸问题
• 状态压缩：使用二维数组存储路由器×信号强度的状态信息

技术特点

• 状态转移：通过放大器边进行信号强度的状态转移
• 可行性剪枝：利用流量限制进行状态剪枝
• 结果组合：将正向和反向传播的结果组合得到最终解

复杂度分析

• 状态空间：O(n × s)，其中n ≤ 100，s ≈ 31623
• 每个状态需要处理O(m)条边
• 总体复杂度：O(T × n × s × m)，在题目约束下可接受

该算法通过巧妙的双向状态传播和状态范围限制，有效地解决了带约束的路径优化问题，能够在合理时间内找到最优解。