最长k可重区间集问题
题目描述
给定实直线 \(\text{L}\) 上 \(n\) 个开区间组成的集合 \(\mathbf{I}\)，和一个正整数 \(k\)，试设计一个算法，从开区间集合 \(\mathbf{I}\) 中选取出开区间集合 \(\mathbf{S}\subseteq\mathbf{I}\)，使得在实直线 \(\text{L}\) 上的任意一点 \(x\)，\(\text{S}\) 中包含 \(x\) 的开区间个数不超过 \(k\)，且 \(\sum_{z\in\text{S}}\lvert z\rvert\) 达到最大（\(\lvert z\rvert\) 表示开区间 \(z\) 的长度）。
这样的集合 \(\mathbf{S}\) 称为开区间集合 \(\mathbf{I}\) 的最长 \(k\) 可重区间集。\(\sum_{z\in\text{S}}\lvert z\rvert\) 称为最长 \(k\) 可重区间集的长度。
对于给定的开区间集合 \(\mathbf{I}\) 和正整数 \(k\)，计算开区间集合 \(\mathbf{I}\) 的最长 \(k\) 可重区间集的长度。
输入格式
输入的第一行有 \(2\) 个正整数 \(n\) 和 \(k\)，分别表示开区间的个数和开区间的可重叠数。接下来的 \(n\) 行，每行有 \(2\) 个整数，表示开区间的左右端点坐标 \(l,r\)，数据保证 \(l<r\)。
输出格式
输出最长 \(k\) 可重区间集的长度。
样例 #1
样例输入 #1
4 2
1 7
6 8
7 10
9 13
样例输出 #1
15
提示
对于 \(100\%\) 的数据，\(1\le n\le 500\)，\(1\le k\le 3\)。
题解
考虑某点重叠不超过 $ k $ 和网络流中的流量限制非常相似，于是可以类似建图：
- 离散化
- 每个区间左端点向右端点连一条价值为 \(len\) ，流量为\(1\)的边
- 离散化后的点每点向其右边的点连一条流量为\(k\)，价值为\(0\)的边.
- 从原点释放\(k\)的流量
直接跑费用流即可。
此题启发我们网络流的题目思考每一条流的意义是什么，同时要注意找增广路的过程实际和反悔过程同时进行。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
int f=1,j=0;
char w=getchar();
while(!isdigit(w)){
if(w=='-')f=-1;
w=getchar();
}
while(isdigit(w)){
j=j*10+w-'0';
w=getchar();
}
return f*j;
}
const int N=5001,M=200001;
int head[N],to[M],fro[M],val[M],flo[M],tail=1;
int n,K,fl[N],va[N];
int s,t,cnt,ans;
int dig[N],tot,L[N],R[N],par[N],fr[N],fa[N];
bool inque[N];
inline void addlin(int x,int y,int a,int b){
to[++tail]=y;
fro[tail]=head[x];
head[x]=tail;
flo[tail]=a,val[tail]=b;
to[++tail]=x;
fro[tail]=head[y];
head[y]=tail;
flo[tail]=0,val[tail]=-b;
return ;
}
bool spfa(int last){
deque<int>p;
for(int i=1;i<=cnt;i++)fl[i]=inque[i]=fr[i]=fa[i]=0,va[i]=-1;
fl[s]=last,va[s]=0;
p.push_back(s);
while(!p.empty()){
int u=p.front();p.pop_front();
inque[u]=false;
for(int k=head[u];k;k=fro[k]){
int x=to[k];
if(!flo[k]||va[x]>=va[u]+val[k])continue;
va[x]=va[u]+val[k];
fl[x]=min(fl[u],flo[k]);
fr[x]=k,fa[x]=u;
if(!inque[x])inque[x]=true,p.push_back(x);
}
}
return fl[t]!=0;
}
signed main(){
n=rd(),K=rd();
s=++cnt,t=++cnt;
for(int i=1;i<=n;i++)L[i]=dig[++tot]=rd(),R[i]=dig[++tot]=rd();
sort(dig+1,dig+1+tot);
tot=unique(dig+1,dig+1+tot)-dig-1;
for(int i=0;i<=tot;i++)par[i]=++cnt;
for(int i=1;i<=tot;i++)addlin(par[i-1],par[i],K,0);
addlin(s,par[0],K,0),addlin(par[tot],t,K,0);
for(int i=1;i<=n;i++){
int len=R[i]-L[i];
L[i]=lower_bound(dig+1,dig+1+tot,L[i])-dig;
R[i]=lower_bound(dig+1,dig+1+tot,R[i])-dig;
addlin(par[L[i]],par[R[i]],1,len);
}
while(K&&spfa(K)){
K-=fl[t];
ans+=fl[t]*va[t];
for(int u=t;u!=s;u=fa[u]){
flo[fr[u]]-=fl[t];
flo[fr[u]^1]+=fl[t];
}
}
printf("%d",ans);
return 0;
}