1930: [Shoi2003]pacman 吃豆豆

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1969 Solved: 461
[Submit][Status][Discuss]

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

HINT

N < = 2000

Source

[Submit][Status][Discuss]

题目大意：
　　两个 PACMAN 吃豆豆。一开始的时候，PACMAN 都在坐标原点的左下方，豆豆都在右上方。

PACMAN 走到豆豆处就会吃掉它。PACMAN 行走的路线很奇怪，只能向走或者向上走，他们行走的路线不可以相交。

请你帮这两个 PACMAN 计算一下，他们俩加起来最多能吃掉多少豆豆。

解析：
　　每个点拆成两个，之间连一条流量为1，费用为1的边；
　　如果从一个点出发可以到达另一个点，就将前一个点的出点连向后一个点的入点
　　跑费用流。但是这样显然是会TLE的
　　如果i能到j，j能到k，那么显然无需连i->k这条边这是一个剪枝
　　加了这个剪枝之后可能会WA 因此还要考虑一个点经过多次的情况
　　即每个点从入点向出点再连一条流量为1，费用为0的边
　　加了这个之后就能过了剪枝不强但是没有什么情况能把这个卡掉
　　MS是可以证明复杂度是根号级别的

//204 ms

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
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;
}
const int N=4005;
const int inf=0x3f3f3f3f;
struct node{int x,y;}g[N];
struct edge{int v,cap,cost,next;}e[N*1000];int tot=1,head[N];
int n,m,ans,S,T,dis[N],Prev[N],flow[N],q[N*20];
bool vis[N];
bool cmp(const node &a,const node &b){
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
void add(int x,int y,int z,int cost){
    e[++tot].v=y;e[tot].cap=z;e[tot].cost=cost;e[tot].next=head[x];head[x]=tot;
    e[++tot].v=x;e[tot].cap=0;e[tot].cost=-cost;e[tot].next=head[y];head[y]=tot;
}
bool spfa(){
    for(int i=S;i<=T;i++) vis[i]=0,dis[i]=-1;
    //int h=0,t=1; RE*32!!!
    //改：用下面的unsigned short或用循环队列 
    unsigned short h=0,t=1;q[t]=S;dis[S]=0;flow[S]=inf;
    while(h!=t){
        int x=q[++h];vis[x]=0;
        for(int i=head[x];i;i=e[i].next){
            if(e[i].cap&&dis[e[i].v]<dis[x]+e[i].cost){
                dis[e[i].v]=dis[x]+e[i].cost;
                Prev[e[i].v]=i;
                flow[e[i].v]=min(flow[x],e[i].cap);
                if(!vis[e[i].v]){
                    vis[e[i].v]=1;
                    if(dis[e[i].v]>dis[x])
                        q[h--]=e[i].v;
                    else
                        q[++t]=e[i].v;
                }
            }
        }
    }
    return dis[T]!=-1;
}
void augment(){
    for(int i=T;i!=S;i=e[Prev[i]^1].v){
        e[Prev[i]].cap-=flow[T];
        e[Prev[i]^1].cap+=flow[T];
    }
    ans+=dis[T]*flow[T];
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) g[i].x=read(),g[i].y=read();
    sort(g+1,g+n+1,cmp);
    int sink=n<<1|1,sour=sink+1;S=0;T=sour+1;
    for(int i=1;i<=n;i++){
        add(sink,i,1,0);
        add(i,i+n,1,0);
        add(i,i+n,1,1);
        add(i+n,sour,1,0);
    }
    for(int i=1;i<=n;i++){
        int tmp=-1;
        for(int j=i-1;j;j--){
            if(g[j].y<=g[i].y&&g[j].y>tmp){
                tmp=g[j].y;
                add(j+n,i,2,0);
            }
        }
    }
    add(S,sink,2,0);
    add(sour,T,2,0);
    while(spfa()) augment();
    printf("%d",ans);
    return 0;
}

//=================================================================

dp:

首先建出图，f[i][j]表示a吃到了i点，b吃到了j点的最大值，转移的时候转移拓扑序小的那一维，如果i拓扑序小于j，那么转移到f[k][j]，否则转移到f[i][k],建出的图边数也要优化，不然会超时。优化的方法是假如i,j连边，那么如果有一条边(i,k),x[k]>x[j]并且y[k]>y[j]那么(i,k)这条边就没有必要存在了。因为先取(i,j)在去(j,k)会比直接取(i,k)要好。

//612 ms

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=10005;
const int M=2005;
struct node{int x,y;}g[N];
struct edge{int v,next;}e[N*300];int tot,head[N];
int n,cnt,T,rd[N],id[N],ID[N],q[N*2];
int f[M][M];
inline void add(int x,int y){
    e[++tot].v=y;e[tot].next=head[x];head[x]=tot;
    e[++tot].v=x;e[tot].next=head[y];head[y]=tot;
}
inline bool cmp(const node &a,const node &b){
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
inline void top_sort(){
    unsigned short h=0,t=1;q[t]=0;
    while(h!=t){
        int x=q[++h];
        id[x]=++cnt;
        ID[cnt]=x;
        for(int i=head[x];i;i=e[i].next){
            if(--rd[e[i].v]==0){
                q[++t]=e[i].v;
            }
        }
    }
}
inline void dp(int x,int y){
    for(int i=head[x];i;i=e[i].next){
        int a=e[i].v,b=y;
        if(id[a]>id[b]) swap(a,b);
        if(a!=b)
            f[a][b]=max(f[a][b],f[x][y]+1);
        else
            f[a][b]=max(f[a][b],f[x][y]);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&g[i].x,&g[i].y);
    sort(g+1,g+n+1,cmp);
    for(int i=1;i<=n;i++){
        int tmp=2e9;
        for(int j=i+1;j<=n;j++){
            if(i!=j&&g[i].x<=g[j].x&&g[i].y<=g[j].y&&g[j].y<tmp){
                tmp=g[j].y;
                rd[j]++;
                add(i,j);
            }
        }
    }
    T=n+1;
    for(int i=1;i<=n;i++){
        add(0,i);rd[i]++;
        add(i,T);rd[T]++;
    }
    top_sort();
    for(int i=1;i<=cnt;i++){
        for(int j=i;j<=cnt;j++){
            dp(ID[i],ID[j]);
        }
    }
    printf("%d",f[T][T]-1);
    return 0;
}