2595: [Wc2008]游览计划
Description
.jpg)
Input
第一行有两个整数，N和 M，描述方块的数目。
接下来 N行， 每行有 M 个非负整数， 如果该整数为 0， 则该方块为一个景点；
否则表示控制该方块至少需要的志愿者数目。 相邻的整数用 （若干个） 空格隔开，
行首行末也可能有多余的空格。
Output
由 N + 1行组成。第一行为一个整数，表示你所给出的方案
中安排的志愿者总数目。
接下来 N行，每行M 个字符，描述方案中相应方块的情况：
z ‘_’（下划线）表示该方块没有安排志愿者；
z ‘o’（小写英文字母o）表示该方块安排了志愿者；
z ‘x’（小写英文字母x）表示该方块是一个景点；
注：请注意输出格式要求，如果缺少某一行或者某一行的字符数目和要求不
一致（任何一行中，多余的空格都不允许出现） ，都可能导致该测试点不得分。
Sample Input
0 1 1 0
2 5 5 1
1 5 5 1
0 1 1 0
Sample Output
xoox
___o
___o
xoox
HINT
对于100%的数据，N,M,K≤10，其中K为景点的数目。输入的所有整数均在[0,2^16]的范围内
Source
斯坦纳树裸题(SPFA + 状压DP)
其实wy今天是第一天接触斯坦纳树（Steiner Tree）呢
从成都回来的zh学长给蒟蒻wy详细地介绍了Steiner Tree
首先， Steiner Tree与最小生成树相似， 都是在给定边集中找最短网络使给定点联通
然而， Steiner Tree中可以有额外的点
可以确定的是， 满足题意的路径是一颗斯坦纳树
由于这道题给定点（K）≤ 10 我们可以用10位的2进制来表示点的连接状态
定义f[x][y][o]表示以（x, y）为根的树满足o的状态时需要的最小代价
易得
<1> f[x][y][o] <= f[x][y][o1] + f[x][y][o2] - a[x][y] (o = o1 | o2)
<2> f[x][y][o] <= f[p][q][o] + a[x][y] (点（x, y）与 点（p, q）相邻)
对于式<1>, 我们用普通的DP维护即可
对于式<2>, 对于相邻两点， 我们不能直接确定它们的更新关系
类似的， 我们可以想到最短路中的dist[]数组更新
对于dist[u1] <= dist[u2] + w[u1][u2]
我们可以采用SPFA的方式更新维护
那么， 最先入队列的应该是哪些点呢?
显然， 在维护完式<1>后 f[x][y][o]不为最大值的点可以先入队列更新其他点
综上所述，
我们可以依次枚举状态o,
对于某一状态， 我们枚举点（x, y） 用 式<1> 维护更新
对于f[x][y][o]不为INF的点， 我们将其加入队列
每次枚举完所有点后， SPFA用 式<2> 维护更新状态为o的情况
答案输出问题只需要在转移时记下前驱， 在输出前递归标记最优路径即可
#include <queue>
#include <cstdio>
using namespace std;
const int MaxO = 1 << 10;
const int INF = 1e9;
int N, M, cnt, opt, xi, yi;
int a[11][11];
int f[11][11][MaxO];
int vis[11][11];
int xx[4] = {0, 0, 1, -1};
int yy[4] = {1, -1, 0, 0};
struct state{
int x, y, opt;
state(int a = 0, int b = 0, int o = 0) {
x = a, y = b, opt = o;
}
}pre[11][11][MaxO];
queue <state> Q;
void SPFA(int o) {
while (!Q.empty()) {
state u = Q.front();
Q.pop();
vis[u.x][u.y] = 0;
for (int k = 0; k < 4; ++k) {
int x = u.x + xx[k];
int y = u.y + yy[k];
if (x < 1 || x > N) continue;
if (y < 1 || y > M) continue;
if (f[x][y][o] > f[u.x][u.y][o] + a[x][y]) {
f[x][y][o] = f[u.x][u.y][o] + a[x][y];
pre[x][y][o] = state(u.x, u.y, o);
if (!vis[x][y]) {
vis[x][y] = 1;
Q.push(state(x, y, o));
}
}
}
}
}
void Dfs(int x, int y, int o) {
if (!pre[x][y][o].opt) return;
vis[x][y] = 1;
state u = pre[x][y][o];
Dfs(u.x, u.y, u.opt);
if (u.x == x && u.y == y) Dfs(u.x, u.y, o - u.opt);
}
int main()
{
for (int i = 1; i <= 10; ++i)
for (int j = 1; j <= 10; ++j)
for (int o = 0; o < MaxO; ++o)
f[i][j][o] = INF;
scanf("%d%d", &N, &M);
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;
if (!xi) xi = i, yi = j;
}
}
opt = (1 << cnt) - 1;
for (int o = 1; o <= opt; ++o) {
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j) {
for (int op = o & o - 1; op; op = o & op - 1)
if (f[i][j][o] > f[i][j][op] + f[i][j][o - op] - a[i][j]) {
f[i][j][o] = f[i][j][op] + f[i][j][o - op] - a[i][j];
pre[i][j][o] = state(i, j, op);
}
if (f[i][j][o] != INF) vis[i][j] = 1, Q.push(state(i, j, o));
}
SPFA(o);
}
Dfs(xi, yi, opt);
printf("%d\n", f[xi][yi][opt]);
for (int i = 1; i <= N; ++i, printf("\n"))
for (int j = 1; j <= M; ++j)
if (!a[i][j]) printf("x");
else
if (vis[i][j]) printf("o");
else printf("_");
}
评论 (0)
