记录编号	285254	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 最长k可重区间集	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-07-21 15:44:48	内存使用	0.68 MiB

#include <algorithm> 
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int INF=233333333;
const int maxn=2010,maxm=20010;
int cnt,fir[maxn],nxt[maxm],to[maxm],cap[maxm],val[maxm],dis[maxn],path[maxn];
struct data{
    int l,r,v;
    bool operator <(const data A)const{
        if(l!=A.l)
            return l<A.l;
        return r<A.r;     
    }
}ar[maxn];

struct data2{
    int a,pos;
    bool operator <(const data2 A)const{
        if(a!=A.a)
            return a<A.a;
        return pos<A.pos;     
    }
}br[maxn];

void addedge(int a,int b,int c,int v)
{
    nxt[++cnt]=fir[a];to[cnt]=b;cap[cnt]=c;val[cnt]=v;fir[a]=cnt;
}
int S,T;
int Spfa()
{
    queue<int>q;
    memset(dis,-1,sizeof(dis));
    q.push(S);dis[S]=0;
    while(!q.empty())
    {
        int node=q.front();q.pop();
        for(int i=fir[node];i;i=nxt[i])
            if(cap[i]&&dis[node]+val[i]>dis[to[i]]){
                dis[to[i]]=val[i]+dis[node];
                path[to[i]]=i;
                q.push(to[i]);
            }
    }
    return dis[T]==-1?0:dis[T]; 
}

int Aug()
{
    int p=T,f=INF;
    while(p!=S)
    {
        f=min(f,cap[path[p]]);
        p=to[path[p]^1];
    }
    p=T;
    while(p!=S)
    {
        cap[path[p]]-=f;
        cap[path[p]^1]+=f;
        p=to[path[p]^1];
    }
    return f;
}

int MCMF()
{
    int ret=0,d;
    while(d=Spfa())
        ret+=Aug()*d;
    return ret;    
}

int cont;
void Init()
{
    cnt=1;cont=0;
    memset(fir,0,sizeof(fir));
}

int main()
{
	freopen("interv.in","r",stdin);
	freopen("interv.out","w",stdout);
	int n,k;
    {
        Init();
        scanf("%d%d",&n,&k);    
        for(int i=1;i<=n;i++){
            scanf("%d%d",&ar[i].l,&ar[i].r);
			ar[i].v=ar[i].r-ar[i].l;
		}
        sort(ar+1,ar+n+1);
        for(int i=1;i<=n;i++){
            br[i*2-1].a=ar[i].l;br[i*2].a=ar[i].r;
            br[i*2-1].pos=br[i*2].pos=i;
        }
        sort(br+1,br+2*n+1);
        for(int i=1;i<=n;i++)
            ar[i].l=ar[i].r=0;
        for(int i=1;i<=2*n;i++)
        {
            int p=br[i].pos;
            if(!ar[p].l){
                ar[p].l=++cont;
            }
            else{
                ar[p].r=++cont;
            }
        }

        S=0;T=cont+1;
        for(int i=0;i<cont+1;i++)
            addedge(i,i+1,k,0),addedge(i+1,i,0,0); 
        for(int i=1;i<=n;i++)
            addedge(ar[i].l,ar[i].r,1,ar[i].v),addedge(ar[i].r,ar[i].l,0,-ar[i].v);
        printf("%d\n",MCMF());        
    }
    return 0;
}