首页 > 其他 > 详细

「网络流」王子

时间:2020-06-14 17:10:28      阅读:37      评论:0      收藏:0      [点我收藏+]

  假期的考题,假期没好好改,,qwq

  一个点的颜色会对一段编号连续的区间产生影响

  所以把区间串成一串,假定一开始都是颜色B,现修改一些合适的位置为A

  做法一(mikufun orz)

    考虑将每个点由颜色B变为A的这个动作作为一条边 跨越链上的一段 来体现变色

    有流的 跨过链上一点的边数 必须属于区间[P,K-Q]

    考虑怎么限制上界,从S给1的流量设为K-Q

    考虑怎么限制下界,从i给i+1的流量设为K-Q-P

    配套地,要跑的是最大费用最大流,即保证K-Q流满

    这样不仅永远能保证留下Q个颜色B,而且流满K-Q才能保证$(flow_tot=K-Q)-(flow_i\leq K-Q-P)\geq P$

    即修改足够数量的P,这种做法我想不到,但是流出的结果就是对的,不知道怎么想到。

  做法二(skyh orz)

    考虑令链上的流量表示区间内修改了颜色的点数,那么流量限制为[P,K-Q]

    上下界最大费用流?可是有正环,spfa就挂了

    回想一般的上下界是怎么做的,钦定下界流满然后留出到上界的流量,再跑补偿流

    这样做一般是想付出尽量少的代价,spfa不会通过正代价环更新回自己

    想付出尽量多的代价就钦定正边一开始全部选满,建反向边代价为负

    那么只剩下负边了,是同样效果,

    不合法的钦定会在补偿流的时候跑那条反向边退回去,所以还是我太菜了qwq

    

    做法二的这种消环的方法大概在所有无源汇的场景下都没有什么问题...

「网络流」王子

原文:https://www.cnblogs.com/yxsplayxs/p/13125340.html

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