首页 > 其他 > 详细

*LOJ#6227. 「网络流 24 题」最长k可重线段集问题

时间:2018-04-25 15:12:41      阅读:223      评论:0      收藏:0      [点我收藏+]

$n \leq 500$条平面上的线段,问一种挑选方法,使得不存在直线$x=p$与挑选的直线有超过$k$个交点,且选得的直线总长度最长。

横坐标每个点开一个点,一条线段就把对应横坐标连一条容量一费用(-长度)的边;点$x$向点$x+1$连一条容量$k$费用0的边。这里的$k$边限制的是直线上其他不经过这里的地方。

这里有个trick就是有与$x$轴垂直的线段。直接判掉会wa。为此把坐标扩大两倍,如果$l=r$那么$r++$否则$l++$,相当于把一个点拆成两个。

*LOJ#6227. 「网络流 24 题」最长k可重线段集问题

原文:https://www.cnblogs.com/Blue233333/p/8944809.html

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