本人水平有限,只能到洛谷来问问了。
很多资料上写,先跑一遍无源汇可行流,再把附加边撤掉从汇点到源点跑一遍最大流,可行流减去最大流就是答案。我认为这看起来挺对的,这样也可以过 Loj 上的模板题。
直到刚刚我被某题的这么一组数据干爆了。
2 1 0 10
源点是 1,汇点是 2。不做处理直接输出的结果是 -10。看起来是因为从汇点到源点流的时候流出了一条从源点的角度看并不合法的最大流。
但是似乎只要在可行流为 0 的时候直接退出,那就没有数据能让它挂掉了。
求问:
- 这种情况的本质是什么?
- 上下界最大流会不会有类似的情况?
- 为什么可行流不为 0 的时候这么做没有问题?
另外那题有个特殊性质,就是每条边的上下界要么是 [0,x],要么是 [x,x]。不知道有没有关系。