题目大意：给出一些平面上的点，你有两个吃豆人，从一个点出发，这个吃豆人可以吃到当前点右上方的点，
BZOJ 1930 SHOI 2003 pacman 吃豆豆 费用流
。问这两个吃豆人最多可以吃到多少豆子。思路：我已經吧不相交的条件去掉了。。
不加优化的费用流模型很明显
超级源->源 flow2 cost0
汇->超级汇 flow2 cost0
下面是拆点
i<< 1 ->i<< 1|1 flow1 cost1
对于从点i能够到达点j的情况
i<< 1|1 - >j<< 1 flow1 cost0
然后跑朴素费用流，很明显T掉了。一组能够卡的数据，所有点都是(i,i)，2000个点跑这个算法会出现n^2条边。
优化的出发点也是很明显的。如果有三个点i,j,k能够从i到j到k，那么我们就肯定不会走i->k这条边，那么这个边就不用加进去。
还有一些小细节，详见代码。
CODE：
#include<queue>#include<cstdio>#include<cstring>#include<iostream>#include #define MAX 4010#define MAXE 4100000#define INF 0x3f3f3f3f#define S 0#define _S 1#define T (MAX - 1)#define _T (MAX - 2)using namespace std;struct Point{ int x,y; bool operator<(const Point &a)const { if(x == a.x) return y< a.y; return x< a.x; } void Read() { scanf("%d%d",&x,&y); }}point[MAX];struct MinCostMaxFlow{ int head[MAX],total; int next[MAXE],aim[MAXE],flow[MAXE],cost[MAXE]; int f[MAX],from[MAX],p[MAX]; bool v[MAX]; MinCostMaxFlow() { total = 1; } void Add(int x,int y,int f,int c) { next[++total] = head[x]; aim[total] = y; flow[total] = f; cost[total] = c; head[x] = total; } void Insert(int x,int y,int f,int c) { Add(x,y,f,c); Add(y,x,0,-c); } bool SPFA() { static queue<int>q; while(!q.empty()) q.pop(); memset(f,0x3f,sizeof(f)); memset(v,false,sizeof(v)); f[S] = 0; q.push(S); while(!q.empty()) { int x = q.front(); q.pop(); v[x] = false; for(int i = head[x]; i; i = next[i]) if(flow[i] && f[aim[i]] >f[x] + cost[i]) { f[aim[i]] = f[x] + cost[i]; if(!v[aim[i]]) v[aim[i]] = true,q.push(aim[i]); from[aim[i]] = x; p[aim[i]] = i; } } return f[T] != INF; } int EdmondsKarp() { int re = 0; while(SPFA()) { int max_flow = INF; for(int i = T; i != S; i = from[i]) max_flow = min(max_flow,flow[p[i]]); for(int i = T; i != S; i = from[i]) { flow[p[i]] -= max_flow; flow[p[i]^1] += max_flow; } re += f[T] * max_flow; } return re; }}solver;int cnt;int main(){ cin >>cnt; for(int i = 1; i<= cnt; ++i) point[i].Read(); sort(point + 1,point + cnt + 1); for(int i = 1; i<= cnt; ++i) { int _min = INF; for(int j = i + 1; j<= cnt; ++j) { if(point[j].y< _min && point[j].y >= point[i].y) solver.Insert(i<< 1|1,j<< 1,2,0); if(point[j].y >= point[i].y) _min = min(_min,point[j].y); } } for(int i = 1; i<= cnt; ++i) { solver.Insert(i<< 1,i<< 1|1,1,-1); solver.Insert(i<< 1,i<< 1|1,1,0); solver.Insert(_S,i<< 1,1,0); solver.Insert(i<< 1|1,_T,1,0); } solver.Insert(S,_S,2,0); solver.Insert(_T,T,2,0); cout<< -solver.EdmondsKarp()<< endl; return 0;}