- 2024 Summer MnZn Final Round Part Ⅱ
数据是否过水
-
张博勇& @ 2024-8-10 12:04:28
题目中没有保证从 出发所有点都可到达，因此拓扑排序应该先预处理出所有能到达的点。
放过了没有预处理的 toposort+DP。
5 条评论
-
tomxi @ 2024-8-10 13:24:29
-
@ 2024-8-10 13:24:57
能过lrx的hack
-
@ 2024-8-10 13:35:07
看不到代码，但是感觉跑反图挺有道理的%
-
-
@ 2024-8-10 13:21:14
直接建反图，按照常规的思路跑top就可以了
-
@ 2024-8-10 13:12:18对于“数据是否过水”：确实。
对于“拓扑排序应该先预处理出所有能到达的点”：啊？
-
@ 2024-8-10 13:19:58
应该是根据能遍历到的边处理每个点的入度，还是说有更好的方法，请求指点/bx
-
-
@ 2024-8-10 12:28:23
比如
5 4 1 1 1 1 1 1 2 5 4 4 3 3 2 -
@ 2024-8-10 12:27:34
不是，这个得看数据中有没有保证只有1入度为0的问题吧
🤔 1-
@ 2024-8-10 12:50:13
这与从1出发是否能到达所有点是等效的。
-
@ 2024-8-10 13:19:29
不等效，仅仅从1出发不一定通过top序到达其他点，比如lrx给定那个hack，
-
- 1