「BZOJ1930」[SHOI2003] pacman吃豆豆

2014年6月14日5,69311

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

题解

最后一个点卡spfa费用流。。。再加上本机跑得慢才过了7个点。。。

什么时候再想想dp做法。。。

费用流就是拆点随便搞

#include<cstdio>
#include<iostream>
#define inf 0x7fffffff
#define ll long long
using namespace std;
inline ll read()
{
    ll 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,cnt=1,ans,T,S;
int x[2005],y[2005];
int head[4005],q[4005],dis[4005],from[4005];
bool inq[4005],used[2005];
struct data{int to,from,next,v,c;}e[6000005];
void ins(int u,int v,int w,int c)
{
    e[++cnt].to=v;e[cnt].from=u;
    e[cnt].next=head[u];head[u]=cnt;
    e[cnt].v=w;e[cnt].c=c;
}
void insert(int u,int v,int w,int c)
{ins(u,v,w,c);ins(v,u,0,-c);}
bool spfa()
{
    for(int i=0;i<=T;i++)dis[i]=-inf;
    int t=0,w=1;
    dis[0]=0;q[0]=0;inq[0]=1;
    while(t!=w)
    {
        int now=q[t];t++;if(t==4005)t=0;
        for(int i=head[now];i;i=e[i].next)
            if(e[i].v&&e[i].c+dis[now]>dis[e[i].to])
            {
                dis[e[i].to]=e[i].c+dis[now];
                from[e[i].to]=i;
                if(!inq[e[i].to])
                {
                    inq[e[i].to]=1;
                    q[w++]=e[i].to;
                    if(w==4005)w=0;
                }
            }
        inq[now]=0;
    }
    if(dis[T]==-inf)return 0;
    return 1;
}
void dfs()
{
    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^1].v+=x;}
}
int main()
{
	//freopen("pacman.in","r",stdin);
	//freopen("pacman.out","w",stdout);
	n=read();T=2*n+2;S=T-1;
	for(int i=1;i<=n;i++)
	    x[i]=read(),y[i]=read();
	for(int i=1;i<=n;i++)
	{
	    insert(S,i,1,0);
	    insert(i,i+n,1,1);
	    insert(i+n,T,1,0);
	}
	insert(0,S,2,0);
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	        if(x[i]<=x[j]&&y[i]<=y[j]&&i!=j)
	            insert(i+n,j,1,0);
	while(spfa())dfs();
	printf("%d",ans);
	return 0;
}

#include<cstdio>

#include<iostream>

#define inf 0x7fffffff

#define ll long long

using namespace std;

inline ll read()

{

ll 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,cnt=1,ans,T,S;

int x[2005],y[2005];

int head[4005],q[4005],dis[4005],from[4005];

bool inq[4005],used[2005];

struct data{int to,from,next,v,c;}e[6000005];

void ins(int u,int v,int w,int c)

{

e[++cnt].to=v;e[cnt].from=u;

e[cnt].next=head[u];head[u]=cnt;

e[cnt].v=w;e[cnt].c=c;

}

void insert(int u,int v,int w,int c)

{ins(u,v,w,c);ins(v,u,0,-c);}

bool spfa()

{

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

int t=0,w=1;

dis[0]=0;q[0]=0;inq[0]=1;

while(t!=w)

{

int now=q[t];t++;if(t==4005)t=0;

for(int i=head[now];i;i=e[i].next)

if(e[i].v&&e[i].c+dis[now]>dis[e[i].to])

{

dis[e[i].to]=e[i].c+dis[now];

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

if(!inq[e[i].to])

{

inq[e[i].to]=1;

q[w++]=e[i].to;

if(w==4005)w=0;

}

inq[now]=0;

}

if(dis[T]==-inf)return 0;

return 1;

}

void dfs()

{

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^1].v+=x;}

}

int main()

{

//freopen("pacman.in","r",stdin);

//freopen("pacman.out","w",stdout);

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

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

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

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

{

insert(S,i,1,0);

insert(i,i+n,1,1);

insert(i+n,T,1,0);

}

insert(0,S,2,0);

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

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

if(x[i]<=x[j]&&y[i]<=y[j]&&i!=j)

insert(i+n,j,1,0);

while(spfa())dfs();

printf("%d",ans);

return 0;

}

« 「BZOJ2661」[BJ WC2012] 连连看「BZOJ2324」[ZJOI2011] 营救皮卡丘 »

pjfer

这种无聊题都能ac……

pjfer

l路过……

aaaaa

此题需要优化连边，暴力连边会TLE

NaApe

其实这题建边时加个剪枝貌似就不会MLE了

hzwer

原来如此，我还以为一定要手动增广当时就懒得写了

huanghongxun

记得用优先栈就过了。。

lyx

我一开始自己去写这道题，交上去TLE(很奇怪的是内存0kb，时间0ms)，交了总共7次都是这样。。。一怒之下试了一下学长的代码。。。结果剧情相同。。。我对自己这种遭遇感到醉了

skydec

这都能过！跪大神！

hzwer

没过啊

黑暗世界

你手动第一次增广就能过了

ju_ruo

这种无聊题简直了

hzwer.com _ Home | http://hzwer.com

「BZOJ1930」[SHOI2003] pacman吃豆豆

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论