警示后人 关于isap

P3376 【模板】网络最大流

Joker_Fish @ 2024-04-06 14:52:09

这个问题是我在写二分图最大匹配的时候默写板子失败后发现的,想了想还是发这里了。

isap跑的时候如果已经用的流量已经超过送过来的流量就要及时返回,不能直接break然后进入抬升高度环节。

就像这样:if(flow==used)return flow; 其中flow为当前传过来的流量,used为已经使用的流量。而不是 if(flow==used)break;。这样是会进入后面的抬升高度环节导致答案变小。原理应该是只有拥有没流完的流量的时候才需要抬升高度把剩下的的流下去(本人猜测)。


by D_FANG @ 2024-07-14 10:28:04

@Joker_Fish 感激不尽!


|