2595: [Wc2008]游览计划
Time Limit: 10 Sec Memory Limit: 256 MBSec Special JudgeSubmit: 1931 Solved: 943[][][]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
HINT
对于100%的数据，N,M,K≤10，其中K为景点的数目。输入的所有整数均在[0,2^16]的范围内
Source
分析：裸的斯坦纳树.
感觉没什么好说的，就是要记录路径比较麻烦，我的做法是在一个结构体里记录每个f值的地图，每次更新就在地图的基础上更新.
#include#include #include #include #include using namespace std;const int inf = 0x7ffffff,dx[] = { 0,0,1,-1},dy[] = { 1,-1,0,0};struct node{ int x,y;} e[120];struct node2{ int tot,v; int p[11][11]; void init() { memset(p,0,sizeof(p)); tot = 0; v = inf; } void push(node temp) { p[temp.x][temp.y] = 1; }} f[12][12][(1 << 10) + 1],pos;int n,m,a[12][12],tot,maxn,ans = inf,b[12][12],vis[12][12],cnt;node2 hebing(node2 a,node2 b){ node2 temp; temp.init(); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (a.p[i][j] || b.p[i][j]) temp.p[i][j] = 1; } return temp;}void spfa(int sta){ memset(vis,0,sizeof(vis)); queue q; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { node temp; temp.x = i; temp.y = j; q.push(temp); vis[i][j] = 1; } while (!q.empty()) { node u = q.front(); q.pop(); int x = u.x,y = u.y; vis[x][y] = 0; for (int i = 0; i <= 3; i++) { int nx = x + dx[i],ny = y + dy[i]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) { if (f[nx][ny][sta].v > f[x][y][sta].v + a[nx][ny]) { f[nx][ny][sta] = f[x][y][sta]; f[nx][ny][sta].v = f[x][y][sta].v + a[nx][ny]; node temp; temp.x = nx; temp.y = ny; f[nx][ny][sta].push(temp); if (!vis[nx][ny]) { vis[nx][ny] = 1; q.push(temp); } } } } }}int main(){ 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] == 0) { node temp; temp.x = i; temp.y = j; e[++tot] = temp; } } maxn = (1 << tot) - 1; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int k = 0; k <= maxn; k++) f[i][j][k].init(); for (int i = 1; i <= tot; i++) { int x = e[i].x,y = e[i].y; f[x][y][1 << (i - 1)].v = 0; } for (int sta = 0; sta <= maxn; sta++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int k = sta; k; k = (k - 1) & sta) { if(f[i][j][sta].v > f[i][j][k].v + f[i][j][sta ^ k].v - a[i][j]) { f[i][j][sta] = hebing(f[i][j][k],f[i][j][sta ^ k]); f[i][j][sta].v = f[i][j][k].v + f[i][j][sta ^ k].v - a[i][j]; } } } } spfa(sta); } pos.init(); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (f[i][j][maxn].v < ans) { ans = f[i][j][maxn].v; pos = f[i][j][maxn]; } } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (pos.p[i][j]) { b[i][j] = 2; cnt += a[i][j]; } for (int i = 1; i <= tot; i++) { int x = e[i].x,y = e[i].y; b[x][y] = 1; } printf("%d\n",cnt); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (b[i][j] == 0) putchar('_'); if (b[i][j] == 1) putchar('x'); if (b[i][j] == 2) putchar('o'); } printf("\n"); } return 0;}