bzoj:2595: [Wc2008]游览计划

时间：2024-09-17 00:07:02

Description

bzoj:2595: [Wc2008]游览计划

bzoj:2595: [Wc2008]游览计划

Input

第一行有两个整数，N和 M，描述方块的数目。 
接下来 N行， 每行有 M 个非负整数， 如果该整数为 0， 则该方块为一个景点；
否则表示控制该方块至少需要的志愿者数目。 相邻的整数用 （若干个） 空格隔开，
行首行末也可能有多余的空格。

Output

由 N + 1行组成。第一行为一个整数，表示你所给出的方案
中安排的志愿者总数目。 
接下来 N行，每行M 个字符，描述方案中相应方块的情况： 
z  ‘_’（下划线）表示该方块没有安排志愿者； 
z  ‘o’（小写英文字母o）表示该方块安排了志愿者； 
z  ‘x’（小写英文字母x）表示该方块是一个景点； 
注：请注意输出格式要求，如果缺少某一行或者某一行的字符数目和要求不
一致（任何一行中，多余的空格都不允许出现） ，都可能导致该测试点不得分。

Sample Input

4 4
0 1 1 0
2 5 5 1
1 5 5 1
0 1 1 0

Sample Output

6
xoox
___o
___o
xoox
斯坦纳树……说白了就是把树形dp和状压dp一起搞……
#include<queue>

#include<cstdio>

#include<algorithm>

using namespace std;

struct na{

    int x,y,k;

    na(){

        x=-;

    }

    na(int xx,int yy,int kk):x(xx),y(yy),k(kk){}

};

int n,m,num=,y;

int map[][],bi[][];

int dp[][][(<<)+];

bool bo[][][(<<)+],mp[][];

na ro[][][(<<)+];

queue <na> q;

const int INF=1e8;

const int fx[]={,,,-},fy[]={,-,,};

inline void spfa(){

    register int k,xx,yy,kk;

    while(!q.empty()){

        na no=q.front();

        q.pop();

        bo[no.x][no.y][no.k]=;

        for (k=;k<;k++){

            xx=no.x+fx[k];yy=no.y+fy[k];kk=no.k|bi[xx][yy];

            if (xx<||yy<||xx>=n||yy>=m) continue;

            if (dp[xx][yy][no.k|bi[xx][yy]]>dp[no.x][no.y][no.k]+map[xx][yy]){

                dp[xx][yy][kk]=dp[no.x][no.y][no.k]+map[xx][yy];

                ro[xx][yy][kk]=no;

                if (!bo[xx][yy][kk]){

                    bo[xx][yy][kk]=;

                    q.push(na(xx,yy,kk));

                }

            }

        }

    }

}

inline void dfs(int x,int y,int k){

    mp[x][y]=;

    if (ro[x][y][k].x==-) return;

    dfs(ro[x][y][k].x,ro[x][y][k].y,ro[x][y][k].k);

    if (ro[x][y][k].x==x&&ro[x][y][k].y==y) dfs(x,y,(k^ro[x][y][k].k)|bi[x][y]);

}

int main(){

    register int i,j,k,x;

    scanf("%d%d",&n,&m);

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

    for (j=;j<m;j++){

        scanf("%d",&map[i][j]);

        if (!map[i][j]) bi[i][j]=<<num,num++;

    }

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

    for (j=;j<m;j++)

    for (k=;k<<<num;k++) dp[i][j][k]=(bi[i][j]&&(bi[i][j]==k))?:INF;

    for (k=;k<<<num;k++){

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

        for (j=;j<m;j++){

            if (bi[i][j]&&!(bi[i][j]&k)) continue;

            for (x=k;x;x=(x-)&k){

                y=dp[i][j][x|bi[i][j]]+dp[i][j][(k^x)|bi[i][j]]-map[i][j];

                if (y<dp[i][j][k]) dp[i][j][k]=y,ro[i][j][k]=na(i,j,x|bi[i][j]);

            }

            if (dp[i][j][k]!=INF) q.push(na(i,j,k)),bo[i][j][k]=;

        }

        spfa();

    }

    k--;

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

    for (j=;j<m;j++)

    if (bi[i][j]){

        printf("%d\n",dp[i][j][k]);

        na o=ro[i][j][k];

        dfs(i,j,k);

        for (int ii=;ii<n;ii++){

            for (int jj=;jj<m;jj++)

            if (map[ii][jj]==) printf("x");else

            if (mp[ii][jj]) printf("o");else printf("_");

            printf("\n");

        }

        return ;

    }

}

相关文章