A6621 | $「网络流 24 题」最长 k 可重区间集$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定实直线 $ L $ 上 $ n $ 个开区间组成的集合 $ I $，和一个正整数 $ k $，试设计一个算法，从开区间集合 $ I $ 中选取出开区间集合 $ S \subseteq I $，使得在实直线 $ L $ 的任何一点 $ x $，$ S $ 中包含点 $ x $ 的开区间个数不超过 $ k $。且 $ \sum\limits_{z \in S} | z | $ 达到最大。这样的集合 $ S $ 称为开区间集合 $ I $ 的最长 $ k $ 可重区间集。$ \sum\limits_{z \in S} | z | $ 称为最长 $ k $ 可重区间集的长度。 对于给定的开区间集合 $ I $ 和正整数 $ k $，计算开区间集合 $ I $ 的最长 $ k $ 可重区间集的长度。

文件的第 $ 1 $ 行有 $ 2 $ 个正整数 $ n $ 和 $ k $，分别表示开区间的个数和开区间的可重迭数。 接下来的 $ n $ 行，每行有 $ 2 $ 个整数 $ l_i $ 和 $ r_i $，表示开区间的左右端点坐标，**注意可能有 $ l_i > r_i $，此时请将其交换**。

输出最长 $ k $ 可重区间集的长度。

输入 #1

输出 #1

C++ 编辑器

输入

输出