1432: 「网络流 24 题」最长 k 可重线段集问题
[Creator : ]
Description
给定平面 $\text{xoy}$ 上 $n$ 个开线段组成的集合 $\text{I}$，和一个正整数 $k$，试设计一个算法。
从开线段集合 $\text{I}$ 中选取出开线段集合 $\text{S}\in \text{I}$，
使得在 x 轴上的任何一点 $\text{p}$，$\text{S}$ 中与直线 $\text{x}=\text{p}$ 相交的开线段个数不超过 $\text{k}$，
且 $\sum_{\text{z} \in \text{S}}$ 达到最大。
这样的集合 $\text{S}$ 称为开线段集合 $\text{I}$ 的最长 $\text{k}$ 可重线段集的长度。
对于任何开线段 $\text{z}$，设其断电坐标为 $( x_0 , y_0 )$ 和 $( x_1 , y_1 )$，
则开线段 $\text{z}$ 的长度 $|\text{z}|$ 定义为：$|\text{z}|=\lfloor \sqrt{ ( x_1 - x_0 ) ^ 2 + ( y_1 - y_0 )^2 } \rfloor$
对于给定的开线段集合 $\text{I}$ 和正整数 $\text{k}$，计算开线段集合 $\text{I}$ 的最长 $\text{k}$ 可重线段集的长度。
从开线段集合 $\text{I}$ 中选取出开线段集合 $\text{S}\in \text{I}$，
使得在 x 轴上的任何一点 $\text{p}$，$\text{S}$ 中与直线 $\text{x}=\text{p}$ 相交的开线段个数不超过 $\text{k}$，
且 $\sum_{\text{z} \in \text{S}}$ 达到最大。
这样的集合 $\text{S}$ 称为开线段集合 $\text{I}$ 的最长 $\text{k}$ 可重线段集的长度。
对于任何开线段 $\text{z}$，设其断电坐标为 $( x_0 , y_0 )$ 和 $( x_1 , y_1 )$，
则开线段 $\text{z}$ 的长度 $|\text{z}|$ 定义为：$|\text{z}|=\lfloor \sqrt{ ( x_1 - x_0 ) ^ 2 + ( y_1 - y_0 )^2 } \rfloor$
对于给定的开线段集合 $\text{I}$ 和正整数 $\text{k}$，计算开线段集合 $\text{I}$ 的最长 $\text{k}$ 可重线段集的长度。
Input
文件的第一行有二个正整数 $\text{n}$ 和 $\text{k}$，分别表示开线段的个数和开线段的可重迭数。
接下来的 $\text{n}$ 行，每行有 4 个整数，表示开线段的 2 个端点坐标。
接下来的 $\text{n}$ 行，每行有 4 个整数，表示开线段的 2 个端点坐标。
Output
程序运行结束时，输出计算出的最长k可重线段集的长度。
Constraints
$1\leq n\leq 500$
$1 \leq k \leq 13$
$1 \leq k \leq 13$
Sample 1 Input
4 2
1 2 7 3
6 5 8 3
7 8 10 5
9 6 13 9
Sample 1 Output
17