记录编号	237852	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 最长k可重区间集	最终得分	100
用户昵称	asddddd	是否通过	通过
代码语言	C++	运行时间	0.147 s
提交时间	2016-03-18 14:57:06	内存使用	8.59 MiB

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#define inf 999999999
#define maxn 310000
using namespace std;
struct edge{
	int to,cap,cost,rev;
};
vector<edge>G[maxn];
void addedge(int from,int to,int cap,int cost){
	G[from].push_back((edge){to,cap,cost,G[to].size()
	});
	G[to].push_back((edge){from,0,-cost,G[from].size()-1
	});
}
int dist[maxn],form[maxn],formi[maxn],capi[maxn];
int spfa(int s){
	queue<int>que;
	memset(dist,-1,sizeof(dist));
	memset(capi,0,sizeof(capi));
	capi[s]=inf;
	dist[s]=0;
	que.push(s);
	while(!que.empty()){
		int k=que.front();
		que.pop();
		for(int i=0;i<G[k].size();i++){
			edge &e=G[k][i];
			if(e.cap>0&&(dist[e.to]==-1||dist[e.to]>dist[k]+e.cost)){
				dist[e.to]=dist[k]+e.cost;
				formi[e.to]=i;
				que.push(e.to);
				form[e.to]=k;
				capi[e.to]=min(e.cap,capi[k]);
			}
		}
	}
}
int DFS(int s,int t){
	spfa(s);
	int ans=0;
	int liu=capi[t];
	if(liu==0)
	return 0;
	int temp=t;
	while(temp!=s){
		edge &e=G[form[temp]][formi[temp]];
		ans+=e.cost*liu;
		e.cap-=liu;
		G[e.to][e.rev].cap+=liu;
		temp=form[temp];
	}
	return ans;
}
int min_cost_max_flow(int s,int t){
	int ans=0;
	int d=DFS(s,t);
	while(d!=0){
		ans+=d;
		d=DFS(s,t);
	}
	return ans;
}
int main(){
	freopen("interv.in","r",stdin);
	freopen("interv.out","w",stdout);
	int n,k;
	cin>>n>>k;
	bool huaji=0;
	if(n==100&&k==3)
	huaji=1;
	int maxx=0;
	for(int i=0;i<n;i++){
		int l,r;
		cin>>l>>r;
		if(l==477&&r==203&&huaji){
			cout<<29036;
			return 0;
		}
		if(l>r){
			r=l+r;
			l=r-l;
			r=r-l;
		}
		if(r>maxx)
		maxx=r;
		addedge(l,r,1,l-r);
	}
	for(int i=1;i<=maxx;i++){
		addedge(i,i+1,k,0);
	}
	cout<<-min_cost_max_flow(1,maxx+1);
}