BZOJ3205:[Apio2013]机器人 斯坦纳树+单位边权多源最短路

思路:

就是一堆机器人合并起来,看起来天然的生成树模型吗.

令\(f[i][j][x][y]\)表示区间\([i,j]\)的机器人合并到位置\((x,y)\)使得最小推动次数,模仿斯坦纳树,我们有以下两种转移:

\[f[i][j][x][y]=f[i][j][x'][y']+1\]

\[f[i][j][x][y]=f[i][k][x][y]+f[k+1][j][x][y]\]

第二种转移直接暴力即可.

对于第一种转移,我们则可以利用一次最短路spfa求解.

至于如何构图呢?我们需要预处理出对于机器人目前在的每一个位置,我们将机器人推动一个方向后最终处于的位置.

我煞笔被坑了几次:首先机器人最终是可以停在转动器位置的.

如果我们每次暴力枚举,会T,因此只能利用记忆化搜索来做.

反正这个预处理坑了我好久.(太弱不解释

可是只有这些优化还是不能AC的!

我们每次暴力spfa的耗时还是过长了.

这怎么优化?

我们发现边权都是1,下面介绍一种神奇的方法:

我们维护两个队列,首先将所有的点按照距离从小到大的顺序加入第二个队列中,随后进行松弛,每次选择两个队列队头距离比较小的点取出进行松弛,并将松弛后的点加入第一个队列中,这样就起到了优先队列的作用,且不用带一个\(log\),这样做是线性的.

这样才能AC!

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
#define INF 0x1f1f1f1f
 
#define N 10
#define W 510
#define H 510
int n,w,h;
char s[W][H];
     
int f[N][N][W][H],tclock,vis[W][H][4];
 
int nowi,nowj;
struct Ins{
    short x,y;
    Ins(){}
    Ins(int _x,int _y):x(_x),y(_y){}
    bool operator<(const Ins&B)const{return f[nowi][nowj][x][y]<f[nowi][nowj][B.x][B.y];}
}vec[W][H][4];
 
const int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
 
queue<Ins>q1,q2;
 
Ins seq[W*H],tmp[W*H];int siz,rk[W*H],t[200010],cnt[200010];
inline void add(int x,int c,int v){if(t[x]!=v)t[x]=v,cnt[x]=0;cnt[x]+=c;}
inline int ask(int x,int v){if(t[x]!=v)t[x]=v,cnt[x]=0;return cnt[x];}
 
int sig;
inline void Rdxsort(){
    ++sig;
    int Max=0;register int i;int x,y;
    for(i=1;i<=siz;++i)add(f[nowi][nowj][x=seq[i].x][y=seq[i].y],1,sig),Max=max(Max,f[nowi][nowj][x][y]);
    for(i=1;i<=Max;++i)add(i,ask(i-1,sig),sig);
    for(i=1;i<=siz;++i)rk[i]=ask(f[nowi][nowj][x=seq[i].x][y=seq[i].y],sig),add(f[nowi][nowj][x][y],-1,sig),tmp[rk[i]]=seq[i];
    for(i=1;i<=siz;++i)seq[i]=tmp[i];
}
 
bool inq[W][H];
inline void work(){
    register int i,j,k;
    for(i=1;i<=siz;++i)q2.push(seq[i]),inq[seq[i].x][seq[i].y]=1;
    Ins t,to;int d1,d2;
    while(!q1.empty()||!q2.empty()){
        if(q1.empty())t=q2.front(),q2.pop();
        else if(q2.empty())t=q1.front(),q1.pop();
        else{
            d1=f[nowi][nowj][q1.front().x][q1.front().y];
            d2=f[nowi][nowj][q2.front().x][q2.front().y];
            if(d1<d2)t=q1.front(),q1.pop();else t=q2.front(),q2.pop();
        }
        for(inq[t.x][t.y]=k=0;k<4;++k){
            if((to=vec[t.x][t.y][k]).x!=INF&&f[nowi][nowj][to.x][to.y]>f[nowi][nowj][t.x][t.y]+1){
                f[nowi][nowj][to.x][to.y]=f[nowi][nowj][t.x][t.y]+1;
                if(!inq[to.x][to.y])inq[to.x][to.y]=1,q1.push(to);
            }
        }
    }
}
 
Ins calc(int x,int y,int v){
    if(vis[x][y][v]==tclock)return Ins(-1,-1);vis[x][y][v]=tclock;
    if(!(vec[x][y][v].x==0&&vec[x][y][v].y==0))return vec[x][y][v];
    int nowv=v;if(s[x][y]=='A')nowv=(v+1)%4;if(s[x][y]=='C')nowv=(v+3)%4;
    int tx=x+dx[nowv],ty=y+dy[nowv];
    if(s[tx][ty]=='x')return vec[x][y][v]=Ins(x,y);
    return vec[x][y][v]=calc(tx,ty,nowv);
}
 
int main(){
    scanf("%d%d%d",&n,&h,&w);
    register int i,j,k,p,q;
    for(i=1;i<=w;++i)scanf("%s",s[i]+1);
    memset(f,0x1f,sizeof f);
    int id;
    for(i=1;i<=w;++i)for(j=1;j<=h;++j)if(s[i][j]>='1'&&s[i][j]<='9')id=s[i][j]-'0',f[id][id][i][j]=0;
 
    for(i=0;i<=w+1;++i)s[i][0]=s[i][h+1]='x';
    for(j=0;j<=h+1;++j)s[0][j]=s[w+1][j]='x';
 
    for(i=1;i<=w;++i)for(j=1;j<=h;++j)if(s[i][j]!='x')
        for(k=0;k<4;++k)
            ++tclock,vec[i][j][k]=calc(i,j,k);
 
    for(int l=1;l<=n;++l)for(i=1;i+l-1<=n;++i){
        j=i+l-1;
        for(k=i;k<j;++k)for(p=1;p<=w;++p)for(q=1;q<=h;++q)f[i][j][p][q]=min(f[i][j][p][q],f[i][k][p][q]+f[k+1][j][p][q]);
        siz=0;for(p=1;p<=w;++p)for(q=1;q<=h;++q)if(f[i][j][p][q]!=INF)seq[++siz]=Ins(p,q);
        nowi=i,nowj=j,Rdxsort();
        work();
    }
 
    int ans=INF;
    for(i=1;i<=w;++i)for(j=1;j<=h;++j)ans=min(ans,f[1][n][i][j]);
 
    if(ans==INF)puts("-1");else printf("%d\n",ans);
 
    return 0;
}