你把边想成点不就对了
by FwbAway @ 2022-12-26 19:40:01
是不是可以dfs
by kimi0705 @ 2022-12-26 19:40:03
什么意思
给定一个 n 个点 m 条边有向图，每个点有一个权值，求一条路径，使路径经过的$ ······ 点·····$权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
by kimi0705 @ 2022-12-26 19:41:36
@[Farewell_Bye](/user/481337)
by kimi0705 @ 2022-12-26 19:41:59
@[kimi0705](/user/637788) 我们之前做的边权题是不是 $i$ 到 $i + 1$ 有一条边，一个权值，现在我们变成了 $i$ 和 $i + 1$ **各**有一个点，和一个权值，这两者不都差不多吗
by FwbAway @ 2022-12-26 19:45:07
知道了每个点的权职然后就知道他连在了哪里，然后又怎么做呢？
是在每一个点上dfs一遍吗？然后取每个点的最大值
by kimi0705 @ 2022-12-26 19:47:35
缩到没法再缩的时候，然后那怎么办啊？
by kimi0705 @ 2022-12-26 19:49:07
哦，我知道了，就是记忆化DFS可以对吧
by kimi0705 @ 2022-12-26 19:54:03
~~去厕所冷静一下~~
by kimi0705 @ 2022-12-26 19:54:31
@[kimi0705](/user/637788) 您可以参考题解。
缩点的功能就是把图变成一个DAG，那么就可以通过递推的方法来计算，也就是直接DP即可
by liangbowen @ 2022-12-26 20:06:40