C++11(clang++ 3.9) 解法, 执行用时: 18ms, 内存消耗: 1000K, 提交时间: 2019-08-22 08:17:32

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e4+10,M=1e6+10;
int n,S,T,v[N],e[N],d[N];
int head[N],nex[M],w[M],to[M],flow[M],tot=1;
struct node{
	int x,y;
}t[N];
int cmp(const node a,const node b){
	if(a.x!=b.x) return a.x<b.x;	return a.y<b.y;
}
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; w[tot]=d; flow[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
int spfa(){
	memset(d,0xcf,sizeof d);	queue<int> q;	q.push(S);
	d[S]=0;	int vis[N]={0};	vis[S]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]>0&&d[to[i]]<d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				v[to[i]]=u; e[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	} 
	return d[T]!=0xcfcfcfcf;
}
int EK(){
	int res=0;
	while(spfa()){
		int mi=0x3f3f3f3f;
		for(int i=T;i!=S;i=v[i])	mi=min(mi,flow[e[i]]);
		for(int i=T;i!=S;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		res+=mi*d[T];
	}
	return res;
}
signed main(){
	cin>>n;	S=4*n+1; T=S+1;	 int m=n+1;
	for(int i=1;i<=n;i++)	cin>>t[i].x>>t[i].y;
	t[0].x=t[0].y=0;
	sort(t+1,t+1+n,cmp);	add(S,0,2,0);
	for(int i=0;i<=n;i++){
		int mi=0;
		for(int j=i+1;j<=n;j++){
			if(t[i].y>t[j].y)	continue;
			if((!mi)||t[j].y<mi){
				add(i+m,j,2,0);	mi=t[j].y;
			}
		}
	}
	add(0,m,2,0);
	for(int i=1;i<=n;i++)	add(i,i+m,1,1),add(i,i+m,1,0),add(i+m,T,2,0);
	cout<<EK()<<endl;
	return 0;
}