bzoj1930 [Shoi2003]pacman 吃豆豆（费用流）

很标准的费用流，但是在建图时需要优化一下。否则spfa跑这种稠密图会T到飞。
贪心的想，如果x可以先到z再到y，则不建边(x,y)。
然后因为经过一个点只有1的贡献，所以要拆点，建图就是S->s,1,0 t->T,1,0 对于每一个点x，建边s->x,1,0 x’->t,1,0 x->x’,1,1 x->x’,1,0.对于每一条边(x,y)，建边x’->y,2,0.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 4010
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m,K,h[N],num=1,dis[N],path[N],T=4001,tot=0,s=4002,t=4003,ans=0;
bool inq[N];
struct point{
    int x,y;
}p[N>>1];
inline bool cmp(point x,point y){return x.y==y.y?x.x<y.x:x.y<y.y;}
struct edge{
    int to,next,w,c;
}data[4010010];
inline void add(int x,int y,int w,int c){
    data[++num].to=y;data[num].next=h[x];h[x]=num;data[num].w=w;data[num].c=c;
    data[++num].to=x;data[num].next=h[y];h[y]=num;data[num].w=0;data[num].c=-c;
}
inline bool spfa(){
    deque<int>q;memset(dis,128,sizeof(dis));memset(path,0,sizeof(path));
    q.push_back(0);inq[0]=1;dis[0]=0;
    while(!q.empty()){
        int x=q.front();q.pop_front();inq[x]=0;
        for(int i=h[x];i;i=data[i].next){
            int y=data[i].to;if(!data[i].w) continue;
            if(dis[x]+data[i].c>dis[y]){
                dis[y]=dis[x]+data[i].c;path[y]=i;
                if(!inq[y]){
                    if(!q.empty()&&dis[y]>dis[q.front()]) q.push_front(y);
                    else q.push_back(y);inq[y]=1;
                }
            }
        }
    }return path[T];
}
int main(){
//  freopen("a.in","r",stdin);
    n=read();
    for(int i=1;i<=n;++i) p[i].x=read(),p[i].y=read();
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;++i) add(i,n+i,1,1),add(i,n+i,1,0),add(s,i,1,0),add(n+i,t,1,0);
    for(int i=1;i<=n;++i){
        int mn=inf;
        for(int j=i+1;j<=n;++j)
            if(p[j].x<mn&&p[j].x>=p[i].x) add(n+i,j,2,0),mn=p[j].x;
    }
    add(0,s,2,0);add(t,T,2,0);
    while(spfa()){
        int now=T,low=1;ans+=dis[T];
        while(path[now]) data[path[now]].w--,data[path[now]^1].w++,now=data[path[now]^1].to;
    }printf("%d\n",ans);
    return 0;
}