社区讨论

90分的问题

P3916图的遍历参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mhj34utg
此快照首次捕获于
2025/11/03 19:57
4 个月前
此快照最后确认于
2025/11/03 19:57
4 个月前
查看原帖
90分大致是TLE第8个点,问题在于(暴力的话):
复杂度是 O(N × (N + M))
当 N = 10⁵,M = 10⁵ 时,总操作数 ≈ 10¹⁰,C++ 也跑不过(1 秒约 10⁸ 操作)
与其“从每个点出发找最大可达点”,不如“从大点出发,反向标记它能到达的所有点”。
因为:
如果点 n 能反向到达点 i,
说明 原图中 i 能到达 n
那么 i 的答案至少是 n
从 n, n-1, ..., 1 依次处理,每个点只被标记一次

回复

1 条回复,欢迎继续交流。

正在加载回复...