bzoj1066: [SCOI2007]蜥蜴

xiaoxiao2021-02-28  8

1066: [SCOI2007]蜥蜴

Time Limit: 1 Sec   Memory Limit: 162 MB Submit: 3978   Solved: 2002 [ Submit][ Status][ Discuss]

Description

  在一个r行c列的网格地图中有一些高度不同的石柱,一些石柱上站着一些蜥蜴,你的任务是让尽量多的蜥蜴逃 到边界外。 每行每列中相邻石柱的距离为1,蜥蜴的跳跃距离是d,即蜥蜴可以跳到平面距离不超过d的任何一个石 柱上。石柱都不稳定,每次当蜥蜴跳跃时,所离开的石柱高度减1(如果仍然落在地图内部,则到达的石柱高度不 变),如果该石柱原来高度为1,则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个 石柱上。

Input

  输入第一行为三个整数r,c,d,即地图的规模与最大跳跃距离。以下r行为石竹的初始状态,0表示没有石柱 ,1~3表示石柱的初始高度。以下r行为蜥蜴位置,“L”表示蜥蜴,“.”表示没有蜥蜴。

Output

  输出仅一行,包含一个整数,即无法逃离的蜥蜴总数的最小值。

Sample Input

5 8 2 00000000 02000000 00321100 02000000 00000000 ........ ........ ..LLLL.. ........ ........

Sample Output

1

HINT

100%的数据满足:1<=r, c<=20, 1<=d<=4

Source

一道很水的题目,数据规模小到不行

结果我瞎XX搞竟然搞了一个小时

太失败了

本来想加一些奇奇怪怪的小优化(找圆方面的)

结果发现数据小得不行,直接最暴力的上就行

然后提交的时候还不停的RE

结果发现我memset的时候习惯打的小优化炸了

我本来习惯打meset(dep,-1,4*(t+5))的(t是汇点)

结果这次傻不拉唧的瞎XX一写(想着随便多memset一点的)

就+上了100

结果就RE了RE了RE了RE了

哇啊啊啊啊啊啊,有够坑的

这告诉我们什么呢

1、不要瞎XX乱搞

2、数组尽量开大一点(当然,注意不要MLE啊,这次RE了之后我就瞎XX乱开大数组,结果还MLE了一次,因为我算内存的时候是按结构体多少个算的,忘记了结构体里面有3个int3个int3个int3个int)

还有这种建图稍微有点复杂的题目

最好把insert输出一下

刚开始没输出时忘记读int是把那一整个01串都进来了

要读char

诶,太菜了太菜了

上我那傻不拉唧的代码:

#include<cstdio> #include<iostream> #include<cstring> const int N=800+100,M=5*1e6,inf=1e8,len=1e5; struct node { int to,next,v; }e[M]; int first[N],cnt=1,s,t,c,dep[N],qu[len],cur[N],bo[N]; int h[10]={-4,-3,-2,-1,0,1,2,3,4},l[10]={-4,-3,-2,-1,0,1,2,3,4}; int fa(int i,int j) { return (i-1)*c+j; } int fb(int u,int v,int i,int j) { return (u-i)*(u-i) +(v-j)*(v-j) ; } void insert(int u,int v,int q) { e[++cnt].to=v;e[cnt].next=first[u];first[u]=cnt;e[cnt].v=q; e[++cnt].to=u;e[cnt].next=first[v];first[v]=cnt;e[cnt].v=0; // printf("std::%d %d %d\n",u,v,q); } bool bfs() { int i=1,j=2; memset(dep,-1,sizeof(dep)); qu[i]=s;dep[s]=0; while(i!=j) { int r=qu[i++];if(i==len) i=0; for(int k=first[r];k;k=e[k].next) if(dep[e[k].to]==-1&&e[k].v>0) { dep[e[k].to]=dep[r]+1; qu[j++]=e[k].to;if(j==len)j=0; } } if(dep[t]==-1) return 0; return 1; } int dfs(int x,int a) { if(x==t||!a) return a; int flow=0; for(int &k=cur[x];k;k=e[k].next) if(e[k].v>0&&dep[e[k].to]==dep[x]+1) { int w=dfs(e[k].to,std::min(e[k].v,a)); a-=w;flow+=w; e[k].v-=w;e[k^1].v+=w; if(!a) break; } if(!flow) dep[x]=-1; return flow; } int main() { int r,d; scanf("%d %d %d",&r,&c,&d); char o; s=0;t=r*c*2+1;int w,ans=0; for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) { std::cin>>o; o-='0'; if(o) w=(i-1)*c+j,insert(2*w-1,2*w,o); } for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) { std::cin>>o; if(o=='L') ans++,w=(i-1)*c+j,insert(s,2*w-1,1); } int fang=d*d; for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) { for(int p=0;p<9;p++) for(int q=0;q<9;q++) { if(!h[p]&&!l[q]) continue; int u=i+h[p],v=j+l[q]; if(fb(u,v,i,j)<=fang) { if(u>=1&&u<=r&&v>=1&&v<=c) insert(fa(i,j)*2,fa(u,v)*2-1,inf); else if(!bo[fa(i,j)])insert(fa(i,j)*2,t,inf),bo[fa(i,j)]=1; } } } while(bfs()) { for(int i=s;i<=t;i++) cur[i]=first[i]; ans-=dfs(s,inf); } printf("%d\n",ans); return 0; }

转载请注明原文地址: https://www.6miu.com/read-1099991.html

最新回复(0)