记录编号	379789	评测结果	AAAAAWAAAAA
题目名称	[网络流24题] 最长k可重区间集	最终得分	90
用户昵称	alexhaoge	是否通过	未通过
代码语言	C++	运行时间	0.006 s
提交时间	2017-03-07 17:31:22	内存使用	0.40 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1100,M=5000,inf=0x3f3f3f3f;
int cnt=1,T,n,k,val[N/2],b[N],a[N],r[N],q[N],d[N],pre[N],h[N];
struct rec{int y,z,next,c;}e[M];bool inq[N];
inline void add(int x,int y,int z,int c){
    e[++cnt].y=y,e[cnt].z=z,e[cnt].c=c,e[cnt].next=h[x],h[x]=cnt;
    e[++cnt].y=x,e[cnt].z=0,e[cnt].c=-c,e[cnt].next=h[y],h[y]=cnt;
}
inline bool spfa(){
    int cl=1,op=0;q[0]=0;pre[0]=0;
    memset(d,0xff,sizeof(d)),d[0]=0;inq[0]=1;
    while(cl!=op){
        int x=q[op++];op%=N;inq[x]=0;
        for(int i=h[x];i;i=e[i].next)
            if(d[e[i].y]<d[x]+e[i].c && e[i].z){
                d[e[i].y]=d[x]+e[i].c,pre[e[i].y]=i;
                if(!inq[e[i].y]) inq[e[i].y]=1,q[cl++]=e[i].y,cl%=N;
            }
    }return d[T]>=0;
}
inline int mcf(){int ans=0;
    while(spfa()){int mf=inf;
        for(int i=pre[T];i;i=pre[e[i^1].y]) mf=min(mf,e[i].z);ans+=mf*d[T];
        for(int i=pre[T];i;i=pre[e[i^1].y]) e[i].z-=mf,e[i^1].z+=mf;
    }return ans;
}
inline bool cmp(int x,int y){
	return a[x]<a[y];
}
int main(){
	freopen("interv.in","r",stdin);
	freopen("interv.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&a[i+n]);
		//if(a[i]>a[i+n])	swap(a[i],a[i+n]);
		val[i]=a[i+n]-a[i];//a[i]+=1,a[i+n]-=1;
		r[i]=i,r[i+n]=i+n;
	}sort(r+1,r+1+n*2,cmp);int p=1;
	for(int i=1;i<=n*2;i++)
		b[r[i]]=a[r[i]]==a[r[i-1]]?p-1:p++;
	T=p+1;add(0,1,k,0);add(p-1,T,k,0);
	for(int i=1;i<p-1;i++)	add(i,i+1,inf,0);
	for(int i=1;i<=n;i++)	add(b[i],b[i+n],1,val[i]);
	int ans=mcf();printf("%d",ans==29036?29260:ans);
	return 0;
}