limuy @ 2024-02-25 22:16:00
第一篇题解的bfs不应该
if(v==t) return 1;这样每次只能增广一条路径，应该在最后判断dis[t]来决定
本题数据过弱测不出来，但我在二分图最大匹配中测出问题，改前1s,改后77ms,附上提交记录 改前 改后
by 幻想繁星 @ 2024-02-25 22:20:21
@limuy 传统的EK好像还真是这么写的。
by sunrise1024 @ 2024-02-25 22:26:33
@limuy 传统EK是这样的，这题似乎为了让比较传统的做法通过数据很水
by limuy @ 2024-02-26 17:04:42
@sunrise1024 @幻想繁星 我说的是这篇题解中的dinic,ek这样写是对的，但是dinic是错的吧
by sunrise1024 @ 2024-02-26 17:14:11
@limuy 有没有一种可能，一次增广多条路径叫做多路增广优化？
但确实题解里不把优化加全很没素质
by limuy @ 2024-02-26 17:45:35
@sunrise1024 啊，我看了看OI-WIKI，居然这只是个常数优化。。二分图匹配居然差了15倍的速度
by 幻想繁星 @ 2024-02-27 21:43:04
@limuy 因为二分图是这样的，单条增广路很小