记录编号	308455	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 最长k可重区间集	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2016-09-18 05:54:27	内存使用	75.94 MiB

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1005,INF=0x3f3f3f3f;
int n,s,t,len=1,head[maxn],x[maxn],y[maxn],N=0;
struct _q{int num,x;}a[maxn<<1];
bool _compl(_q a,_q b){return a.x<b.x;}
bool _compn(_q a,_q b){return a.num<b.num;} 
struct _tree{int to,next,c,f,fee,from;}e[maxn*maxn*4];
void _Set(int prt,int son,int cap,int cost){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len,
	e[len].c=cap,e[len].f=0,e[len].fee=cost,e[len].from=prt;
}
void _set(int prt,int son,int cap,int cost){
	_Set(prt,son,cap,cost),_Set(son,prt,0,-cost);	
}
#define to e[i].to
int _min(int a,int b){return a<b?a:b;}
queue<int>q;bool bein[maxn];int v[maxn],dis[maxn],p[maxn];
bool _run(int &cost){
	while(!q.empty())q.pop();q.push(s);
	memset(bein,false,sizeof(bein)),memset(dis,0x3f,sizeof(dis));
	bein[s]=true,v[s]=INF,dis[s]=0,p[s]=0;int rt,i;
	while(!q.empty()){
		rt=q.front(),q.pop();bein[rt]=false;
		for(i=head[rt];i;i=e[i].next)
		if(e[i].c>e[i].f&&dis[to]>dis[rt]+e[i].fee){
			dis[to]=dis[rt]+e[i].fee,p[to]=i,v[to]=_min(v[rt],e[i].c-e[i].f);
			if(!bein[to])bein[to]=true,q.push(to);	
		}	
	}
	if(dis[t]==INF)return false;
	rt=t,cost+=dis[t]*v[t];
	while(rt^s)
		e[p[rt]].f+=v[t],e[p[rt]^1].f-=v[t],rt=e[p[rt]].from;
	return true;
}
int _run(){
	int cost=0;
	while(_run(cost));
	return -cost;
}
void _in(){
	int n,k,i;scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++){
		scanf("%d%d",&x[i],&y[i]);
		a[++N].x=x[i],a[N].num=N;
		a[++N].x=y[i],a[N].num=N;
	}
	sort(a+1,a+N+1,_compl);a[N].x=N;
	for(i=1;i<N;i++)a[i].x=i,_set(i,i+1,INF,0);
	s=0,t=N+1;_set(s,1,k,0),_set(N,t,INF,0);
	sort(a+1,a+N+1,_compn);
	for(i=1;i<=N;i+=2)
		_set(a[i].x,a[i+1].x,1,x[(i>>1)+1]-y[(i>>1)+1]);
}
void _work(){
	_in();
	printf("%d\n",_run());
}
int main(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("interv.in","r",stdin);
	freopen("interv.out","w",stdout);
#endif
	_work();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
}