[bzoj]1930 pacman吃豆豆

Description

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

Input

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

Output

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

Sample Input

8

8 1

1 5

5 7

2 2

7 8

4 6

3 3

6 4

Sample Output

7

HINT

N < = 2000

Source

拼尽全力优化，最后还是超时1个点。。。

裸的费用流

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 using namespace std;

 const int INF=0x7fffffff;

 struct Edge

 {

     int from,to,v,c,next;

 }E[];

 int node=;

 int head[],from[],dis[],vis[];

 int n,ans,S,T;

 struct point

 {

     int x,y;

 }P[];

 int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-f;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 void ins(int from,int to,int v,int c)

 {

     node++;

     E[node]=(Edge){from,to,v,c,head[from]};

     head[from]=node;

 }

 void insert(int from,int to,int v,int c)

 {

     ins(from,to,v,c);ins(to,from,,-c);

 }

 bool spfa()

 {

     queue<int> Q;

     for(int i=;i<=T;i++) dis[i]=-INF;

     Q.push();dis[]=;vis[]=;

     while(!Q.empty())

     {

         int q=Q.front();Q.pop();

         for(int i=head[q];i;i=E[i].next)

             if(E[i].v>&&dis[q]+E[i].c>dis[E[i].to])

             {

                 dis[E[i].to]=dis[q]+E[i].c;

                 from[E[i].to]=i;

                 if(!vis[E[i].to])

                 {

                     Q.push(E[i].to);

                     vis[E[i].to]=;

                 }

             }

         vis[q]=;

     }

     return dis[T]!=-INF;

 }

 void mcf()

 {

     int x=INF;

     for(int i=from[T];i;i=from[E[i].from])

         x=min(E[i].v,x);

     for(int i=from[T];i;i=from[E[i].from])

     {

         ans+=x*E[i].c;

         E[i].v-=x;E[i^].v+=x;

     }

 }

 bool cmp(point a,point b)

 {

     return a.x<b.x||(a.x==b.x&&a.y<b.y);

 }

 int main()

 {

     n=read();T=*n+;S=T-;

     for(int i=;i<=n;i++)

         P[i].x=read(),P[i].y=read();

     sort(P+,P+n+,cmp);

     insert(,S,,);

     for(int i=;i<=n;i++)

     {

         insert(S,i,,);

         insert(i,i+n,,);

         insert(i,i+n,,);

         insert(i+n,T,,);

     }

     for(int i=;i<=n;i++)

     {

         int inf=INF;

         for(int j=i+;j<=n;j++)

         {

             if(P[i].y<=P[j].y)

             {

                 if(P[j].y<inf)

                     insert(i+n,j,,);

                 inf=min(inf,P[j].y);

             }

         }

     }

     while(spfa())

         mcf();

     printf("%d",ans);

     return ;

 }