若此题变成边权 求做法正确性
查看原帖
若此题变成边权 求做法正确性
1284815
canwen楼主2025/7/25 13:19

怕错了,特地问一下,求大佬解答。

好像挺弱智的一个问题。

若此题变成边权,求一条价值最大的路径,可以重复经过某些边,但是重复的只算一次。

我的做法如下:

用 tarjan 正常把每一个强联通分量缩成一个点 xx,这个点代表这个强连通分量的边权和,接着遍历该强连通分量的每个点的出边 uvu \to v,若 vv 不在该强连通分量内,则添加一条边 xvx \to v,最后像点权的做法一样去跑拓扑得出答案。

是对的吗?如果是错的,请问能不能给出正确做法qwq,有例题也可以

2025/7/25 13:19
加载中...