Cptraser/ 三月 18, 2019/ 2019.3/ 0 comments

    \[f[i][sta] = \min_{s \in sta}{f[i][s] + f[i][\complement_{sta} s] - val[i]}\]

    \[f[i][j] = \min{f[k][j] + val[i]}\]

第一个是从子集转移,第二个类似松弛操作,用SPFA即可。

WC2008游览计划

// luogu-judger-enable-o2
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

const int Maxn=15,inf=2e9,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int N,M,A[Maxn][Maxn],Ans=inf;
int F[Maxn][Maxn][1<<Maxn|5],vis[Maxn][Maxn],B[Maxn][Maxn],Cnt;
struct pt{int x,y,c;}P[Maxn][Maxn][1<<Maxn|5];
struct Node{int x,y;};

queue<Node>Q;
void SPFA(int k){
    while(!Q.empty()){
        Node front=Q.front();Q.pop();vis[front.x][front.y]=0;
        for(int i=0;i<4;i++){
            int tx=front.x+dx[i],ty=front.y+dy[i];
            if(tx<1||ty<1||tx>N||ty>M)continue;
            if(F[front.x][front.y][k]+A[tx][ty]<F[tx][ty][k|B[tx][ty]]){
                F[tx][ty][k|B[tx][ty]]=F[front.x][front.y][k]+A[tx][ty];
                P[tx][ty][k|B[tx][ty]]=(pt){front.x,front.y,k};
                if(!vis[tx][ty])Q.push((Node){tx,ty}),vis[tx][ty]=1;
            }
        }
    }
}

void Find(int x,int y,int k){
    if(!x||!y)return ;pt Now=P[x][y][k];
    vis[x][y]=1,Find(Now.x,Now.y,Now.c);
    if(Now.x==x&&Now.y==y)Find(x,y,(k-Now.c)|B[x][y]);return ;
}

int main()
{
    scanf("%d%d",&N,&M);
    memset(F,127/3,sizeof F);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++){
            scanf("%d",&A[i][j]);
            if(!A[i][j])F[i][j][1<<Cnt]=0,B[i][j]=1<<Cnt,++Cnt;
            F[i][j][0]=A[i][j];
        }
    for(int S=0;S<1<<Cnt;S++){
        for(int i=1;i<=N;i++)
            for(int j=1;j<=M;j++){
                if(!A[i][j]&&!(S&B[i][j]))continue;
                for(int k=S;k;k=S&(k-1)){
                    if(F[i][j][S]>F[i][j][k|B[i][j]]+F[i][j][(S-k)|B[i][j]]-A[i][j]){
                        F[i][j][S]=F[i][j][k|B[i][j]]+F[i][j][(S-k)|B[i][j]]-A[i][j];
                        P[i][j][S]=(pt){i,j,k|B[i][j]};
                    }
                }
                if(F[i][j][S]<inf)Q.push((Node){i,j}),vis[i][j]=1;
            }
        SPFA(S);
    }int xx,yy;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)if(!A[i][j]&&Ans>F[i][j][(1<<Cnt)-1]){
            Ans=F[i][j][(1<<Cnt)-1],xx=i,yy=j;
        }
    printf("%d\n",Ans),Find(xx,yy,(1<<Cnt)-1);
    for(int i=1;i<=N;i++,puts(""))
        for(int j=1;j<=M;j++)putchar(!A[i][j]?'x':(vis[i][j]?'o':'_'));
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*