记录编号	151975	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 最长k可重区间集	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2015-03-12 15:02:12	内存使用	0.50 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=1e9;
int n,i,p,zj1=0,zj2,zj3,k,ans,ST,SD;
struct www{
	int x,y;
	bool operator < (const www& a)const{return x<a.x;}
} poi[1010];
int to[10000]={0},w[10000]={0},ne[10000]={0},r[10000]={0},head[1010]={0},sj=1;
inline void addedge(int u,int v,int W,int R)
{
	to[++sj]=v,ne[sj]=head[u],head[u]=sj,w[sj]=-W,r[sj]=R;
	to[++sj]=u,ne[sj]=head[v],head[v]=sj,w[sj]=W,r[sj]=0;
}

int que[1010]={0},qtail=0,qhead=1;bool flag[1010]={0};
inline void PUSH(int &x)
{que[0]++;flag[x]=1;if(++qtail==1010)qtail=1;que[qtail]=x;}
inline int GET()
{int x=que[qhead];flag[x]=0;que[0]--;if(++qhead==1010)qhead=1;return x;}
/*-----------------------------------------*/

void init()
{
	scanf("%d%d",&n,&k);
	ST=n*2+1,SD=ST+1;
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&zj1,&zj2);
		addedge(i,i+n,zj2-zj1,1);
		poi[i].x=zj1,poi[i].y=i;
		poi[i+n].x=zj2,poi[i+n].y=i+n;
	}
	n*=2;sort(poi+1,poi+(n+1));
	for(i=1;i<n;i++)addedge(poi[i].y,poi[i+1].y,0,INF);
	addedge(ST,poi[1].y,0,k);addedge(poi[n].y,SD,0,k);
}

int dis[1010]={0},pre[1010]={0},pres[1010]={0};
inline bool spfa()
{
	for(i=1;i<=SD;i++)dis[i]=INF;
	dis[ST]=0;PUSH(ST);
	while(que[0])
	{
		zj1=GET();
		for(i=head[zj1];i;i=ne[i])
		if(r[i]&&(dis[to[i]]>dis[zj1]+w[i]))
		{
			dis[to[i]]=dis[zj1]+w[i],pre[to[i]]=zj1,pres[to[i]]=i;
			if(!flag[to[i]])PUSH(to[i]);
		}
	}
	if(dis[SD]==INF)return 0;
	return 1;
}

void work()
{
	for(zj1=SD,zj2=INF;zj1!=ST;zj1=pre[zj1])
	if(r[pres[zj1]]<zj2)zj2=r[pres[zj1]];
	for(zj1=SD;zj1!=ST;zj1=pre[zj1])
	r[pres[zj1]]-=zj2,r[pres[zj1]^1]+=zj2;
	ans+=dis[SD]*zj2;
}
int main()
{
	//freopen("a.txt","r",stdin);
	freopen("interv.in","r",stdin);
	freopen("interv.out","w",stdout);
	init();
	while(spfa())work();
	printf("%d\n",-ans);
}