重边??
查看原帖
重边??
1087763
YOUNGxy楼主2024/5/1 17:36

我的思路是先建边权为0的图缩点,后再加边权为1的边。
但是Tragan缩点后建新图的时候产生的重边不会对结果有影响吗。
比如一个scc向另一个scc连了多条权值为1的边,实际上这多条边只用算一条就可以了。
但是不处理重边的话在拓扑的时候感觉答案会算大,看题解里好像没处理重边。

2024/5/1 17:36
加载中...