bzoj:2595: [Wc2008]游览计划

Description

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=-1;
    }
    na(int xx,int yy,int kk):x(xx),y(yy),k(kk){}
};
int n,m,num=0,y;
int map[11][11],bi[11][11];
int dp[11][11][(1<<10)+1];
bool bo[11][11][(1<<10)+1],mp[11][11];
na ro[11][11][(1<<10)+1];
queue <na> q;
const int INF=1e8;
const int fx[4]={0,0,1,-1},fy[4]={1,-1,0,0};
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]=0;
        for (k=0;k<4;k++){
            xx=no.x+fx[k];yy=no.y+fy[k];kk=no.k|bi[xx][yy];
            if (xx<0||yy<0||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]=1;
                    q.push(na(xx,yy,kk));
                }
            }
        }
    }
}
inline void dfs(int x,int y,int k){
    mp[x][y]=1;
    if (ro[x][y][k].x==-1) 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=0;i<n;i++)
    for (j=0;j<m;j++){
        scanf("%d",&map[i][j]);
        if (!map[i][j]) bi[i][j]=1<<num,num++;
    }
    for (i=0;i<n;i++)
    for (j=0;j<m;j++)
    for (k=0;k<1<<num;k++) dp[i][j][k]=(bi[i][j]&&(bi[i][j]==k))?0:INF;
    for (k=0;k<1<<num;k++){
        for (i=0;i<n;i++)
        for (j=0;j<m;j++){
            if (bi[i][j]&&!(bi[i][j]&k)) continue;
            for (x=k;x;x=(x-1)&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]=1;
        }
        spfa();
    }
    k--;
    for (i=0;i<n;i++)
    for (j=0;j<m;j++)
    if (bi[i][j]){
        printf("%d
",dp[i][j][k]);
        na o=ro[i][j][k];
        dfs(i,j,k);
        for (int ii=0;ii<n;ii++){
            for (int jj=0;jj<m;jj++)
            if (map[ii][jj]==0) printf("x");else
            if (mp[ii][jj]) printf("o");else printf("_");
            printf("
");
        }
        return 0;
    }
}