

$21.$最长k可重区间集问题

题目

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

题解

问题可以看做是求K条权之和最大的不想交路径，每条路径为一些不相交的区间序列。

那么就与之前的数字梯形问题差不多了。

连边直接贴一下BYVoid的吧。我懒得写了

按左端点排序所有区间，把每个区间拆分看做两个顶点$i.a, i.b$，建立附加源$S$汇$T$，以及附加顶点$S'$。

1、连接$S$到$S'$一条容量为$K$，费用为$0$的有向边。 2、从$S'$到每个$i.a$连接一条容量为$1$，费用为$0$的有向边。 3、从每个$i.b$到$T$连接一条容量为$1$，费用为$0$的有向边。 4、从每个顶点$i.a$到$i.b$连接一条容量为$1$，费用为区间长度的有向边。 5、对于每个区间$i$，与它右边的不相交的所有区间$j$各连一条容量为$1$，费用为$0$的有向边。

求最大费用最大流，最大费用流值就是最长$k$可重区间集的长度。

还有一种复杂度更低($O(N)$)的方法 。

离散化所有区间的端点，把每个端点看做一个顶点，建立附加源$S$汇$T$。

1、从$S$到顶点$1$（最左边顶点）连接一条容量为$K$，费用为$0$的有向边。 2、从顶点$2N​$（最右边顶点）到$T​$连接一条容量为$K​$，费用为$0​$的有向边。 3、从顶点$i$到顶点$i+1(i+1\leq 2N)$，连接一条容量为无穷大，费用为$0$的有向边。 4、对于每个区间$[a,b]$，从$a$对应的顶点$i$到$b$对应的顶点$j$连接一条容量为$1$，费用为区间长度的有向边。

求最大费用最大流，最大费用流值就是最长$k$可重区间集的长度。