题目描述
两个PACMAN吃豆豆。一开始的时候，PACMAN都在坐标原点的左下方，豆豆都在右上方。PACMAN走到豆豆处就会吃掉它。PACMAN行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。 请你帮这两个PACMAN计算一下，他们俩加起来最多能吃掉多少豆豆。

输入格式
第一行为一个整数N，表示豆豆的数目。 接下来 N 行，每行一对正整数，表示第i个豆豆的坐标。任意两个豆豆的坐标都不会重合。

输出格式
仅有一行包含一个整数，即两个PACMAN加起来最多能吃掉的豆豆数量

输入输出样例
输入 #1 复制
8
8 1
1 5
5 7
2 2
7 8
4 6
3 3
6 4
输出 #1 复制
7
说明/提示
N < = 2000

纪念自己洛谷第一道黑题。。。。。

看到这道题，我们会想到跑费用流，但是由于点数太多，我们不能一一去连边，这样肯定会TLE，那我们就需要做一些剪枝了，对于每个点先按照x坐标排序，然后对于每个点我们肯定只能连到它右上的点。然后假设我们现在已经连了右上的第一个点，那我们怎么做呢？对于连了这个点的后面的比我们连的这个点y坐标大的话，那么这个点肯定会被我们第一个连的点所相连，这样这个点就是不需要相连的，然后跑一次费用流即可。

AC代码：

#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;
}