「网络流 24 题22」最长k可重线段集问题

题目描述:

给定平面 xoy上 n 个开线段组成的集合 I，和一个正整数 k,试设计一个算法。

从开线段集合I中选取出开线段集合S∈I ,

使得在x轴上的任何一点 p ， S 中与直线 x=p 相交的开线段个数不超过 k ，

且 ∑_z∈S∣z∣达到最大。

这样的集合 S称为开线段集合I 的最长 k可重线段集的长度。

对于任何开线段z，设其断电坐标为(x0,y0)和 (x1,y1)，

则开线段 z 的长度 ∣z∣定义为： ∣z∣=⌊√​(x​1​​−x​0​​)​2​​+(y​1​​−y​0​​)​2​​​​​⌋

对于给定的开线段集合 I 和正整数 k ，计算开线段集合 I 的最长 k 可重线段集的长度。

输入格式:

第一 行有二个正整数 n 和 k ，分别表示开线段的个数和开线段的可重迭数。接下来的 n 行，每行有 4个整数，表示开线段的2 个端点坐标。

输出格式:

程序运行结束时，输出计算出的最长k可重线段集的长度。

样例输入:

4 2
1 2 7 3
6 5 8 3
7 8 10 5
9 6 13 9

样例输出:

17

提示:

1≤n≤500
1≤k≤13

时间限制: 1000ms
空间限制: 256MB

---