怎么做班级网站,建设厅官方网站下载专区,定制网站大概多少钱,网站建设案例机构P3357 最长k可重线段集问题
对于n条开线段#xff0c;选择一个子集使得任意xp和子集相交的直线个数小于等于k#xff0c;并使得选择的线段长度之和最大。
这道题看上去和区间集没有什么区别#xff0c;只是费用发生变化#xff0c;但是要注意一个特殊情况#xff0c;那就…P3357 最长k可重线段集问题
对于n条开线段选择一个子集使得任意xp和子集相交的直线个数小于等于k并使得选择的线段长度之和最大。
这道题看上去和区间集没有什么区别只是费用发生变化但是要注意一个特殊情况那就是线段和x轴垂直的情况这个时候如果还是按照之前的方法连边那么就会出现自环那么在这个点就可以流无限次就无法满足k的限制所以我们要将这样的点进行拆点然后就可以满足限制了。
