跳到主要内容
图灵 OJTURING / ONLINE JUDGE

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

  • ID: 303
  • 传统题
  • 1000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 网络流
  • 图论
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

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

题目描述

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

从开线段集合中选取出开线段集合 ,

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

且 达到最大。

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

对于任何开线段 ,设其断电坐标为和 ,

则开线段 的长度 定义为:

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

输入格式

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

输出格式

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

样例

样例输入

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

样例输出

17

数据范围与提示



题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 201 题。保留原作者与原赛事署名。