因为 i 与 i+1 天点的连边容量为 inf−a[i],而我们想保证最大流为 inf,就需要用 si 到 ti+1 的边去补流量,补的流量也就是 si 到 ti+1 天之间无法过去的流量(最大的 ai),然后补完后最后在 n+1 天重新汇聚成 inf,相当于在 si 天我们就贪心的买了足够这一区间刚好够用的志愿者。
关于区间之间的覆盖也保证,因为当一些流量补到 ti+1 时,那一天的流量也会增加,在最大流过程中就相当于是汇过去的流量变化,为了满足流量的性质(流入等于流出),自然会减少一些补过去的流量
如果 si 在其他区间中也是,会改变这一坨流量的组成,为了满足网络流性质
这道题很好的利用了用最大流满足条件于用网络流性质调整流量,确实好题
和p1251的思考方式还是有较多区别的