算法

先转化题意

在有 \(n\) 个点 \(m\) 条边的有向图上, 从点 \(S\) 开始, 最终到达一个拥有酒吧的点
求途径最大点权和, 其中可以重复经过一个点, 但是点权和不再计算

现在动用一下注意力, 在抽象有向图上不好处理, 我们考虑 \(\rm{DAG}\) 的情况

显然的, 对于一个 \(\rm{DAG}\) , 问题变得简单, 只需要按拓扑序跑 \(\rm{dp}\) 即可

那么考虑将原图缩点成为 \(\rm{DAG}\) 之后怎么处理

显然, 我们直接记录缩点之后的边权和即可

看题解发现 \(\rm{spfa}\) 跑最长路也是可以的

代码

当做强连通分量的板子练一下

总结

简单题