题解思路

问题分析

蚂蚁在有向图上移动，每走一步体力乘以 $\rho < 1$，幸福度是体力与顶点权值的乘积。要求找到从起点出发的路径，使得幸福度总和 $H$ 最大。

关键难点：

• 路径可以是无穷的
• 如果存在高价值的环，无限循环可能获得更大幸福度
• $\rho < 1$ 保证无穷级数收敛

核心思路

1. 有限路径情况

对于有限路径 $v_0 \to v_1 \to \cdots \to v_k$，幸福度为：

$$H = w(v_0) + \rho w(v_1) + \rho^2 w(v_2) + \cdots + \rho^k w(v_k) $$

可以用动态规划求解：

dp[k][v] = 到达v点，走了k步的最大幸福度
转移：dp[k][v] = max{ dp[k-1][u] + ρ^(k-1) * w(v) | 存在边 u→v }

2. 无穷路径情况

如果路径最终进入一个环 $C$ 并无限循环，幸福度为：

$$H = H_{\text{prefix}} + \frac{\rho^L \cdot H_{\text{cycle}}}{1 - \rho^{|C|}} $$

其中：

• $H_{\text{prefix}}$：到达环之前的幸福度
• $H_{\text{cycle}}$：环走一次的幸福度
• $L$：到达环时的步数
• $|C|$：环的长度

算法框架

方法1：有限步DP + 环检测

由于 $\rho < 1$，幸福度会指数衰减，经过足够多步后新贡献可以忽略。

方法2：值迭代（推荐）

类似Bellman-Ford，但考虑衰减因子：

方法3：环检测与优化

对于每个强连通分量，计算其最大平均权重：

完整算法

结合有限路径和环检测

复杂度分析

• 有限步DP：$O(\text{steps} \cdot m)$，steps约100-1000
• 值迭代：$O(\text{iterations} \cdot m)$，iterations约1000
• 环检测：$O(n + m)$
• 总复杂度：在数据范围内可行

实现细节

1. 收敛判断

当连续迭代的价值变化小于 $10^{-6}$ 时可以停止。

2. 精度处理

使用双精度浮点数，注意避免数值误差累积。

3. 环的价值计算

对于环 $v_1 \to v_2 \to \cdots \to v_k \to v_1$，单次价值：

$$H_{\text{cycle}} = \rho w(v_2) + \rho^2 w(v_3) + \cdots + \rho^k w(v_1) $$

无限循环总价值：$\frac{H_{\text{cycle}}}{1 - \rho^k}$

样例分析

样例1

存在环 $2\to 3\to 4\to 2$，单次价值： $H = 0.5\times 8 + 0.25\times 8 + 0.125\times 8 = 7$ 无限循环价值：$\frac{7}{1-0.125} = 8$ 加上前缀 $1\to 2$：$10 + 0.5\times 8 = 14$ 总价值：$10 + 0.5\times 8 + \frac{0.25\times 7}{1-0.125} = 18$

总结

这道题的关键在于：

1. 理解无穷路径：通过环获得几何级数的和
2. 结合有限与无限：可能先走有限路径，然后进入高价值环
3. 收敛性利用：$\rho < 1$ 保证算法会收敛
4. 算法选择：值迭代是较简单且有效的解法

通过值迭代或有限步DP结合环检测，可以求出最大幸福度。