问题分析

我们有：

• $n$ 个开区间 $[l_i, r_i)$
• 正整数 $k$ 表示直线上任意点最多被 $k$ 个区间覆盖
• 每个区间的权重是它的长度 $|z| = r_i - l_i$
• 目标：选择一些区间，使得任意点覆盖数 $\leq k$，且区间总长度最大

网络流建模思路

关键观察

将直线上的所有区间端点离散化，得到一系列坐标点。相邻点之间形成线段。

建图方法

1. 节点：离散化后的所有坐标点（从小到大排序去重）

2. 边：

   • 相邻坐标点之间连边：容量 = $k$，费用 = $0$ → 表示在这段小区间上最多有 $k$ 个区间覆盖
   • 对于每个区间 $[l_i, r_i)$，在离散化坐标中找到对应位置，从 $l_i$ 节点向 $r_i$ 节点连边：
     • 容量 = $1$，费用 = $-(r_i - l_i)$（用负费用求最大权） → 表示选择这个区间，花费为负的区间长度（最小费用流会优先选择）

3. 源点 $S$ 连第一个坐标点，容量 = $k$，费用 = $0$

4. 最后一个坐标点连汇点 $T$，容量 = $k$，费用 = $0$

算法正确性解释

• 相邻坐标点间的容量 $k$ 保证了任意小区间最多被 $k$ 个选择的区间覆盖
• 每个区间边容量 $1$ 保证每个区间最多选一次
• 最小费用流会优先选择费用更小（即原长度更大）的区间
• 最终费用取负就是最大总长度

样例验证

输入：

4 2
1 7
6 8  
7 10
9 13

区间长度：

• $[1,7)$：长度6
• $[6,8)$：长度2
• $[7,10)$：长度3
• $[9,13)$：长度4

离散化坐标：$\{1,6,7,8,9,10,13\}$

建图：

• 相邻坐标点间：容量2，费用0
• 区间边：
  • 1→7：容量1，费用-6
  • 6→8：容量1，费用-2
  • 7→10：容量1，费用-3
  • 9→13：容量1，费用-4
• S→1：容量2，费用0
• 13→T：容量2，费用0

最小费用流结果：费用 = -15
最大总长度 = 15

输出：15

验证：选择区间 $[1,7)$(6) 和 $[9,13)$(4) 和 $[7,10)$(3)？不对，$[1,7)$ 和 $[7,10)$ 在点7重叠？开区间 $[1,7)$ 不包括7，$[7,10)$ 从7开始，在7点不重叠。
实际上最优解是：$[1,7)$(6) + $[7,10)$(3) + $[9,13)$(4) = 13？
检查：$[7,10)$ 与 $[9,13)$ 在 $[9,10)$ 重叠，此时k=2允许。
但样例输出15，应该是 $[1,7)$(6) + $[6,8)$(2) + $[9,13)$(4) + $[7,10)$(3) = 15，在 $[7,8)$ 段有 $[6,8)$ 和 $[7,10)$ 两个区间重叠，符合k=2。

算法步骤

1. 读入 $n, k$ 和所有区间，确保 $l_i \leq r_i$
2. 离散化所有端点坐标
3. 建图：
   • 节点：离散化坐标点
   • 相邻点间边：容量 $k$，费用 $0$
   • 每个区间边：容量 $1$，费用 $-(r_i-l_i)$
   • $S$→第一个点：容量 $k$，费用 $0$
   • 最后一个点→$T$：容量 $k$，费用 $0$
4. 跑 $S$ 到 $T$ 的最小费用最大流
5. 输出：$- \text{总费用}$

复杂度分析

• 坐标点数：最多 $2n = 1000$
• 边数：$O(n)$
• 使用费用流算法在 $n \leq 500, k \leq 3$ 时完全可行

关键点

1. 离散化将无限直线变为有限点集
2. 相邻点间容量k保证任意点覆盖数不超过k
3. 负费用将最大化问题转化为最小费用流
4. 开区间 $[l_i, r_i)$ 在 $r_i$ 处不覆盖，所以连边是 $l_i$ → $r_i$

总结

这道题通过离散化和容量限制将区间选择问题转化为网络流模型，利用最小费用流求解最大权k-可重区间集，是区间调度问题的经典网络流解法。