题目地址：洛谷：【P4294】[WC2008]游览计划 – 洛谷、BZOJ：Problem 2595. — [Wc2008]游览计划

题目描述

从未来过绍兴的小D有幸参加了Winter Camp 2008，他被这座历史名城的秀丽风景所吸引，强烈要求游览绍兴及其周边的所有景点。
为了保证安全与便利，主办方依据路况和治安状况，在非景点的一些方块内安排不同数量的志愿者；在景点内聘请导游（导游不是志愿者）。在选择旅游方案时，保证任意两个景点之间，存在一条路径，在这条路径所经过的每一个方块都有志愿者或者该方块为景点。既能满足选手们游览的需要，又能够让志愿者的总数最少。
现在，希望你能够帮助主办方找到一种最好的安排方案。

输入输出格式

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

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

输入输出样例

输入样例#1：

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

输出样例#1：

6
xoox
___o
___o
xoox

说明

对于100%的数据，N,M,K≤10，其中K为景点的数目。输入的所有整数均在[0,2^16]的范围内

题解

本题的数据范围又好像是个状压DP，那就想个状压DP呗。要状压的状态应该是这个景点有没有被连接上，而DP状态也就可以设计成dp[i][j][S]表示在(i, j)处且上面的状态为S所需的最少志愿者数。a数组表示每个格子需要的志愿者数目。
现在转移变成了一个问题，首先我们可以考虑一个常规的枚举子集的思路：
dp[i][j][S] = \min_{T \subseteq S} \{ dp[i][j][T] + dp[i][j][S \wedge T] - a[i][j] \}
减一次的原因是这个数被加了两次。
但是不能老是从自己转移啊，四个相邻的格子也可以转移，但是有后效性。我们考虑SPFA转移，对于两个相邻的格子，有下面的转移
dp[i][j][S] = \min\{ dp[i'][j'][S] + a[i][j] \}
其中(i', j')与(i, j)相邻。SPFA转移在求最小值的题目中很常见。
上面的这一通思路就是个裸的斯坦纳树。这种问题的模型是：有一个图，要求保留图中最少的边/最小的边权和使得某k个点相互连通。只是这个题需要把上述第二种转移更换为有边相连的点。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 11, INF = 0x3f3f3f3f;
const int fix[2][4] = {{-1, 1, 0, 0}, {0, 0, -1, 1}};

struct Point {
    int x, y;
};

struct Data {
    int x, y, s;
} pre[MAXN][MAXN][1 << MAXN];

int n, m, k, mmp[MAXN][MAXN], dp[MAXN][MAXN][1 << MAXN], sx, sy;
std::queue<Point> que;
bool inque[MAXN][MAXN], ans[MAXN][MAXN];

inline void spfa(int s) {
    while(!que.empty()) {
        int x = que.front().x, y = que.front().y; que.pop(); inque[x][y] = false;
        for(int i = 0; i < 4; i++) {
            int nx = x + fix[0][i], ny = y + fix[1][i];
            if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if(dp[nx][ny][s] > dp[x][y][s] + mmp[nx][ny]) {
                dp[nx][ny][s] = dp[x][y][s] + mmp[nx][ny];
                pre[nx][ny][s] = Data {x, y, s};
                if(!inque[nx][ny]) {
                    que.push(Point {nx, ny}); inque[nx][ny] = true;
                }
            }
        }
    }
}

inline void dfs(int x, int y, int s) {
    if(!pre[x][y][s].s) return;
    ans[x][y] = true;
    dfs(pre[x][y][s].x, pre[x][y][s].y, pre[x][y][s].s);
    if(pre[x][y][s].x == x && pre[x][y][s].y == y) dfs(x, y, s ^ pre[x][y][s].s);
}

int main() {
    n = readint(); m = readint();
    memset(dp, 0x3f, sizeof(dp));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(!(mmp[i][j] = readint())) {
                dp[i][j][1 << (k++)] = 0;
                if(!sx) sx = i, sy = j;
            } 
        }
    }
    if(!k) {
        puts("0");
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) putchar('_');
            putchar('\n');
        }
        return 0;
    }
    for(int s = 1; s < (1 << k); s++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                for(int t = s & (s - 1); t; t = s & (t - 1)) {
                    if(dp[i][j][s] > dp[i][j][t] + dp[i][j][s ^ t] - mmp[i][j]) {
                        dp[i][j][s] = dp[i][j][t] + dp[i][j][s ^ t] - mmp[i][j];
                        pre[i][j][s] = Data {i, j, t};
                    }
                }
                if(dp[i][j][s] < INF) que.push(Point {i, j}), inque[i][j] = true;
            }
        }
        spfa(s);
    }
    printf("%d\n", dp[sx][sy][(1 << k) - 1]);
    dfs(sx, sy, (1 << k) - 1);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(!mmp[i][j]) putchar('x');
            else if(ans[i][j]) putchar('o');
            else putchar('_');
        }
        putchar('\n');
    }
    return 0;
}