很巧妙的建图啊...刚了$1h$也没想出来，最后看的题解
发现这道题并不类似于我们平时做的网络流题，它是在序列上的，且很难建出来二分图的形。
那就让它在序列上待着吧= =
对于一个区间，左端点向右端点连边，流量为$1$，费用为区间长度
对于一个位置$i$，向$i+1$连边，流量为$K$，费用为$0$
为什么要这么建图呢？
假设有$1$流量流到了位置$i$，有两种情况
1.选择一个从i开始的区间$[i,r]$，这点流量流到了$r$位置。而在$(i,r)$内，这点流量不能用于其它区间，达到了限制区间个数的目的，然后我们获得了$r-i$点收益
2.不选任何区间，流量流到了$i+1$位置，为后面的区间提供流量
然后跑最大费用最大流就行了
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 2005
#define M1 100100
#define ll long long
#define dd double
#define inf 0x3f3f3f3f
using namespace std; int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
}
int n,K,S,T;
struct Edge{
int head[N1],to[M1<<],nxt[M1<<],flow[M1<<],dis[M1<<],cte;
void ae(int u,int v,int F,int D)
{
cte++; to[cte]=v; flow[cte]=F; dis[cte]=D;
nxt[cte]=head[u]; head[u]=cte;
}
}e; int que[M1<<],hd,tl,dis[N1],id[N1],flow[N1],use[N1];
int spfa()
{
int x,j,v;
memset(dis,-,sizeof(dis)); memset(flow,,sizeof(flow)); memset(use,,sizeof(use));
hd=,tl=; que[++tl]=S; dis[S]=; use[S]=; flow[S]=inf;
while(hd<=tl)
{
x=que[hd++];
for(j=e.head[x];j;j=e.nxt[j])
{
v=e.to[j];
if( e.flow[j]> && dis[v]<dis[x]+e.dis[j] )
{
dis[v]=dis[x]+e.dis[j];
flow[v]=min(flow[x],e.flow[j]);
que[++tl]=v; id[v]=j; use[v]=;
}
}
use[x]=;
}
return dis[T]!=-;
}
int EK()
{
int tcost=,mxflow=,x;
while(spfa())
{
mxflow+=flow[T]; tcost+=flow[T]*dis[T];
for(x=T;x!=S;x=e.to[id[x]^])
{
e.flow[id[x]]-=flow[T];
e.flow[id[x]^]+=flow[T];
}
}
return tcost;
} int l[N1],r[N1],len[N1],t[N1<<],cnt;
int main()
{
scanf("%d%d",&n,&K);
int i,j,x,y,ma; e.cte=;
for(i=;i<=n;i++)
{
l[i]=gint(),r[i]=gint()-; if(l[i]>r[i]) swap(l[i],r[i]);
t[++cnt]=l[i]; t[++cnt]=r[i]; len[i]=r[i]-l[i]+;
}
sort(t+,t+cnt+); cnt=unique(t+,t+cnt+)-(t+);
for(i=;i<=n;i++) l[i]=lower_bound(t+,t+cnt+,l[i])-t;
for(i=;i<=n;i++) r[i]=lower_bound(t+,t+cnt+,r[i])-t;
S=; T=cnt+;
for(i=;i<=n;i++) e.ae(l[i],r[i]+,,len[i]), e.ae(r[i]+,l[i],,-len[i]);
for(i=;i<=cnt;i++) e.ae(i,i+,K,), e.ae(i+,i,,); e.ae(S,,K,); e.ae(,S,,);
printf("%d\n",EK());
return ;
}