「题解」挖宝藏 treasure

(未完待续)

题目链接:GMOJ 3737/WC2008 游览计划的加强版。

题目

题目描述

数据范围

时空限制

本题有多种解法。

题解

思路

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
using std::max;
#include<queue>
using std::queue;
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}
const int MAXH=10+5;
const int MAXN=10+5;
const int MAXM=10+5;
bool inque[MAXN][MAXM];
int h,n,m;
int a[MAXH][MAXN][MAXM],K[MAXH];
int g[MAXH][MAXN][MAXM],f[MAXH][1<<10][MAXN][MAXM];
queue<int> Qx,Qy;
inline bool SPFA(int,int);
int main(void){
    //freopen("treasure.in","r",stdin);
    //freopen("treasure.out","w",stdout);
    register int i,j,k,ans=INF,deep,status;
    h=read(),n=read(),m=read();
    //scanf("%d%d%d",&h,&n,&m);
    for(i=1;i<=h;++i)
        for(j=1;j<=n;++j)
            for(k=1;k<=m;++k)
                a[i][j][k]=read();
    //scanf("%d",&a[i][j][k]);
    memset(f,0X7F,sizeof(f));//初始化
    memset(f[h+1],0,sizeof(f[h+1]));//初始化
    for(i=1;i<=h;++i){
        K[i]=read();
        //scanf("%d",&K[i]);
        for(j=0;j<K[i];++j){
            static int x,y;
            x=read(),y=read();
            //scanf("%d%d",&x,&y);
            g[i][x][y]|=1<<j;//记录状态
        }
    }
    for(deep=h;deep>=1;--deep){//深度逐渐减小
        register int LMS=(1<<K[deep+1])-1,MS=(1<<K[deep]);
        for(i=1;i<=n;++i)
            for(j=1;j<=m;++j){
                f[deep][MS+g[deep][i][j]][i][j]=f[deep+1][LMS][i][j]+a[deep][i][j];
                f[deep][g[deep][i][j]][i][j]=a[deep][i][j];
            }
        MS=(1<<(++K[deep]))-1;
        for(status=0;status<=MS;++status){
            for(i=1;i<=n;++i)
                for(j=1;j<=m;++j){
                    int l=status;
                    while(l){
                        l=((l-1)&status);//取出状态
                        if(!l)
                            break;
                        if(max(f[deep][l][i][j],f[deep][status-l][i][j])<INF)
                            f[deep][status][i][j]=min(f[deep][status][i][j],f[deep][l][i][j]+f[deep][status-l][i][j]-a[deep][i][j]);
                    }
                }
            SPFA(deep,status);//松弛操作
        }
    }
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            ans=min((int)ans,f[1][(1<<K[1])-1][i][j]);//统计答案
    printf("%d\n",ans);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
inline bool SPFA(int deep,int status){
    register int i,j,x,y,fx,fy;
    static int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j){
            inque[i][j]=true;
            Qx.push((int)i),Qy.push((int)j);
        }
    while(!Qx.empty()){
        x=Qx.front(),y=Qy.front();
        Qx.pop(),Qy.pop();
        for(i=0;i<4;++i){
            fx=x+dx[i],fy=y+dy[i];
            if(fx<1||n<fx||fy<1||m<fy)
                continue;
            if(f[deep][status][x][y]+a[deep][fx][fy]<f[deep][status][fx][fy]){
                f[deep][status][fx][fy]=f[deep][status][x][y]+a[deep][fx][fy];
                if(!inque[fx][fy]){
                    inque[fx][fy]=true;
                    Qx.push((int)fx),Qy.push((int)fy);
                }
            }
        }
        inque[x][y]=false;
    }
    return true;
}