「BZOJ2595」[WC2008]游览计划

Description

从未来过绍兴的小D有幸参加了Winter Camp 2008,他被这座历史名城的秀丽风景所吸引,强烈要求游览绍兴及其周边的所有景点。
主办者将绍兴划分为NNMM(N×M)(N\times M)个分块,如下图(8×8)(8\times 8)

景点含于方块内,且一个方块至多有一个景点。无景点的方块视为路。
为了保证安全与便利,主办方依据路况和治安状况,在非景点的一些方块内安排不同数量的志愿者;在景点内聘请导游(导游不是志愿者)。在选择旅游方案时,保证任意两个景点之间,存在一条路径,在这条路径所经过的每一个方块都有志愿者或者该方块为景点。既能满足选手们游览的需要,又能够让志愿者的总数最少。
例如,在上面的例子中,在每个没有景点的方块中填入一个数字,表示控制该方块最少需要的志愿者数目:

图中用深色标出的方块区域就是一种可行的志愿者安排方案,一共需要20名志愿者。由图可见,两个相邻的景点是直接(有景点内的路)连通的(如沈园和八字桥)。

现在,希望你能够帮助主办方找到一种最好的安排方案。

Input

第一行有两个整数,NNMM,描述方块的数目。
接下来NN行,每行有MM个非负整数,如果该整数为00,则该方块为一个景点;
否则表示控制该方块至少需要的志愿者数目。相邻的整数用(若干个)空格隔开,
行首行末也可能有多余的空格。

Output

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

Sample Input

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

Sample Output

1
2
3
4
5
6
xoox
___o
___o
xoox

HINT

对于100%100\%的数据,N,M,K10N,M,K\leq 10,其中KK为景点的数目。输入的所有整数均在[0,216][0,2^{16}]的范围内

Solution

斯坦纳树的板子题。
只不过要输出方案,开一个prepre数组,第一维表示转移过来的子集是ss,第二表示转移过来的点是ii
如果是通过枚举子集转移的,说明pre[s][x]pre[s][x]pre[s^s'][x']是有放置志愿者的。
如果是通过边转移得到的,说明pre[s][x]pre[s][x']是有放置制原则的,因为pre[s xor s][x]pre[s\ xor\ s'][x]等于00,所以不用管。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 120, M = N * N * 2;
int n, m;
int f[1 << 10][N];
int a[N];
int id[11], tot;
int bin[12];
priority_queue<pii,vector<pii>,greater<pii> >q;
bool vis[N];
int num;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
pii pre[1 << 10][N];
void dijkstra(int *f, int s) {
for(int i = 1; i <= num; ++i) vis[i] = 0;
while(!q.empty()){
pii now = q.top(); q.pop();
int x = now.nd;
if(vis[x]) continue;
vis[x] = 1;
int tx = (x - 1) / m + 1;
int ty = (x - 1) % m + 1;
for(int k = 0; k < 4; ++k) {
int nx = tx + dx[k];
int ny = ty + dy[k];
if(nx < 1 || nx > n || ny <1 || ny > m) continue;
int y = (nx - 1) * m + ny;
if(f[y] > f[x] + a[y]) {
pre[s][y] = mk(s, x);
f[y] = f[x] + a[y];
q.push(mk(f[y], y));
}
}
}
}
bool yy[110];
void dfs(int s, int x) {
yy[x] = 1;
if(pre[s][x].nd == 0) return;
dfs(pre[s][x].fi, pre[s][x].nd);
dfs(s ^ pre[s][x].fi, x);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
int t = (i - 1) * m + j;
a[t] = read();
if(!a[t]) id[++tot] = t;
}
}
bin[0] = 1;
for(int i = 1; i <= tot; ++i) bin[i] = bin[i - 1] << 1;
memset(f,0x3f,sizeof f);
for(int i = 1; i <= tot; ++i) f[(1 << (i - 1))][id[i]] = 0;
int b = (1 << tot);
num = n * m ;
for(int s = 0; s < b; ++s) {
for(int i = 1; i <= num; ++i) {
for(int j = s; j; j = (j - 1) & s) {
if(j == s) continue;
if(f[j][i] + f[s ^ j][i] - a[i] < f[s][i]) pre[s][i] = mk(j, i);
f[s][i] = min(f[s][i], f[j][i] + f[s ^ j][i] - a[i]);
}
q.push(mk(f[s][i], i));
}
dijkstra(f[s], s);
}
int ans = 1e9;
for(int i = 1; i <= num; ++i) ans = min(ans, f[b - 1][i]);
writeln(ans);
for(int i = 1; i <= num; ++i) if(f[b - 1][i] == ans) {
dfs(b - 1, i);
break;
}
for(int i = 1; i <= num; ++i) {
if(a[i] == 0) putchar('x');
else if(yy[i] == 0) putchar('_');
else putchar('o');
if(i % m == 0) puts("");
}
return 0;
}