怕错了,特地问一下,求大佬解答。
好像挺弱智的一个问题。
若此题变成边权,求一条价值最大的路径,可以重复经过某些边,但是重复的只算一次。
我的做法如下:
用 tarjan 正常把每一个强联通分量缩成一个点 xxx,这个点代表这个强连通分量的边权和,接着遍历该强连通分量的每个点的出边 u→vu \to vu→v,若 vvv 不在该强连通分量内,则添加一条边 x→vx \to vx→v,最后像点权的做法一样去跑拓扑得出答案。
是对的吗?如果是错的,请问能不能给出正确做法qwq,有例题也可以