首页 > 其他 > 详细

[CTSC2010]产品销售

时间:2020-12-20 10:43:05      阅读:25      评论:0      收藏:0      [点我收藏+]

先考虑流。
\(s->i\)连流量\(d_i\)费用\(0\)
\(i->t\)连流量\(u_i\)费用\(p_i\)
\(i->i+1\)连流量\(\inf\)费用\(c_i\)
\(i+1->i\)连流量\(\inf\)费用\(m_i\)
然而我们并不能通过此题。
考虑从左到右枚举所有和源点连边的边进行增广。
我们需要找到当前边向左/右的最短路。
当前边向右的最短路:由于我们后面的边都没有增广过,所以我们一定不会走反向边。
可以用一个线段树维护代价。如果一个点和汇点连的边代价变为\(0\),需要把这条边在线段树上删除(赋值为\(\inf\)
当前边向左的最短路:可能会走反向边。如果一条原边被反向边覆盖,则我们一定会走这条边上的反向边。
考虑用另一个线段树维护权值和我们当前反向边的流量。
每次在线段树上找到最小值的位置。
增广流量:\(\min(最小值位置到t的流量,当前点到最小值位置的流量,s到当前点的流量)\)
分析复杂度:一条边在被向右增广时复杂度显然是\(O(n\log_2n)\)
在被向左增广时,由于我们从左到右增广,所以当前边的流量显然会先增加,后减少。最终只会减到\(0\)一次。
而只有减到\(0\)才会贡献复杂度\(O(\log_2n)\)
同时,与源点/汇点相邻的边只有减到\(0\)才会贡献复杂度\(O(\log_2n)\)
所以总时间复杂度\(O(n\log_2n)\)

[CTSC2010]产品销售

原文:https://www.cnblogs.com/ctmlpfs/p/14162569.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!