给定实直线L上的n个开区间，和一个正整数k
选取若干个区间，在保证实直线L上的任意一个点最多被选出区间覆盖k次的情况下，使得这些区间的长度和最大
先把区间按照左端点排序，
考虑到重复其实就代表着相交，
可以把问题转化为选出k组组内不相交区间，使得他们区间长度和最大。
从源点S向每个区间左端点连一条容量1费用0的边，每个区间右端点向汇点T连一条容量1费用0的边。用来限制每条边只能选一次。
每个区间左端点向右端点连一条容量1费用为区间长度的边
每个区间右端点向所有数值比它大的其他区间左端点连一条容量1费用0的边。
求最大费用最大流即可。（将所有费用取相反数然后求最小费用最大流）
代码如下
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int MAXN=;
const int maxn=;
const int INF=~0U>>;
int maxflow=,cost=;
int pre[maxn],vis[maxn],dis[maxn];
int S,Sa,T;
int n,k;
int tot=;
int pointer[maxn];
struct qj{
int l;int r;
}a[maxn];
struct Edge
{
int to,next,cap,op,f,w;
Edge() {};
Edge(int b,int c,int nxt,int num,int flow,int weight) {to=b,cap=c,next=nxt,op=num^,f=flow,w=weight;}
}edge[MAXN];
inline void addedge(int a,int b,int c,int w1)
{
edge[tot]=Edge(b,c,pointer[a],tot,,w1);
pointer[a]=tot++;
edge[tot]=Edge(a,,pointer[b],tot,,-w1);
pointer[b]=tot++;
}
bool cmp(qj A,qj B)
{
return A.l<B.l;
}
void init()
{
memset(pointer,-,sizeof(pointer));
scanf("%d%d",&n,&k);
int l,r;
rep(i,,n)
{
scanf("%d%d",&a[i].l,&a[i].r);
// printf("i=%d l=%d r=%d\n",i,a[i].l,a[i].r);
}
sort(a+,a+n+,cmp);
S=;
Sa=*n+;T=*n+;
addedge(S,Sa,k,);
rep(i,,n)
{
addedge(Sa,i,,);
addedge(i,n+i,,a[i].l-a[i].r);
rep(j,i+,n)
{
if(a[j].l>=a[i].r)
{
addedge(n+i,j,,);
}
}
addedge(n+i,T,,);
}
}
bool spfa(int s,int t)
{
queue<int > q;
rep(i,S,T)
{
dis[i]=INF;
vis[i]=false;
pre[i]=-;
}
dis[S]=;
vis[S]=;
q.push(S);
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=;
for(int j=pointer[u];j!=-;j=edge[j].next)
{
int v=edge[j].to;
if(edge[j].cap-edge[j].f>&&dis[v]>dis[u]+edge[j].w)
{
dis[v]=dis[u]+edge[j].w;
pre[v]=j;
if(!vis[v])
{
vis[v]=;q.push(v);
}
}
}
}
if(pre[T]==-) return false;
else return true;
}
int mcmf()
{
int flow=;
cost=;
while(spfa(S,T))
{
int mi=INF;
for(int i=pre[T];i!=-;i=pre[edge[i^].to])
{
mi=min(mi,edge[i].cap-edge[i].f);
}
for(int i=pre[T];i!=-;i=pre[edge[i^].to])
{
edge[i].f+=mi;
edge[i^].f-=mi;
cost+=edge[i].w*mi;
}
flow+=mi;
}
return flow;
}
int main()
{
freopen("interv0.in","r",stdin);
// freopen("why.txt","w",stdout);
init();
mcmf();
printf("%d",-cost);
return ;
}