好题啊,谈下此题费用流建图理解
查看原帖
好题啊,谈下此题费用流建图理解
728448
mqmhaaaa1楼主2024/12/10 13:47

因为 iii+1i+1 天点的连边容量为 infa[i]inf-a[i],而我们想保证最大流为 infinf,就需要用 sis_iti+1t_i+1 的边去补流量,补的流量也就是 sis_iti+1t_i+1 天之间无法过去的流量(最大的 aia_i),然后补完后最后在 n+1n+1 天重新汇聚成 infinf,相当于在 sis_i 天我们就贪心的买了足够这一区间刚好够用的志愿者。

关于区间之间的覆盖也保证,因为当一些流量补到 ti+1t_i+1 时,那一天的流量也会增加,在最大流过程中就相当于是汇过去的流量变化,为了满足流量的性质(流入等于流出),自然会减少一些补过去的流量

如果 sis_i 在其他区间中也是,会改变这一坨流量的组成,为了满足网络流性质

这道题很好的利用了用最大流满足条件于用网络流性质调整流量,确实好题

和p1251的思考方式还是有较多区别的

2024/12/10 13:47
加载中...