bzoj 2595: [Wc2008]游览计划

题意：

给你一个地图，有些格子是关键格，非关键格有价格。要你选出一些格子使得所有关键格连通，花费最少。

题解：

斯坦纳树裸题，记录一下路径就好了。

代码：

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
int n, m, a[20][20], f[20][20][1030], pre1[20][20][1030], pre2[20][20][1030], cnt = 0, px[4] = {1, 0, -1, 0}, py[4] = {0, 1, 0, -1}, ans = inf, posx, posy;
bool out[20][20];

void spfa(int S)
{
    static queue<int> qx, qy;
    static bool v[20][20];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (f[i][j][S] < inf)
            {
                v[i][j] = 1;
                qx.push(i);
                qy.push(j);
            }
    while (!qx.empty())
    {
        int x = qx.front(), y = qy.front();
        v[x][y] = 0;
        qx.pop(), qy.pop();
        for (int i = 0; i < 4; i++)
        {
            int xx = x + px[i], yy = y + py[i];
            if (xx > 0 && xx <= n && yy > 0 && yy <= m && f[xx][yy][S] > f[x][y][S] + a[xx][yy])
            {
                f[xx][yy][S] = f[x][y][S] + a[xx][yy];
                pre1[xx][yy][S] = -1;
                pre2[xx][yy][S] = i;
                if (!v[xx][yy])
                {
                    v[xx][yy] = 1;
                    qx.push(xx);
                    qy.push(yy);
                }
            }
        }
    }
}
void wk(int x, int y, int S)
{
    out[x][y] = 1;
    if (~pre1[x][y][S])
    {
        wk(x, y, pre1[x][y][S]);
        wk(x, y, pre1[x][y][S] ^ S);
    }
    if (~pre2[x][y][S])
        wk(x - px[pre2[x][y][S]], y - py[pre2[x][y][S]], S);
}
int main()
{
    memset(f, 63, sizeof(f));
    memset(pre1, -1, sizeof(pre1));
    memset(pre2, -1, sizeof(pre2));
    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;
        }
    for (int S = 1; S < (1 << cnt); S++)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                for (int s = S & (S - 1); s; s = S & (s - 1))
                {
                    if (f[i][j][s] + f[i][j][S ^ s] - a[i][j] < f[i][j][S])
                    {
                        f[i][j][S] = f[i][j][s] + f[i][j][S ^ s] - a[i][j];
                        pre1[i][j][S] = s;
                        pre2[i][j][S] = -1;
                    }
                }
        spfa(S);/*
        printf("S: %d\n", S);
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
                printf("%d ", f[i][j][S]);
            puts("");
        }*/
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (f[i][j][(1 << cnt) - 1] < ans)
            {
                ans = f[i][j][(1 << cnt) - 1];
                posx = i;
                posy = j;
            }
    printf("%d\n", ans);
    wk(posx, posy, (1 << cnt) - 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            if (!a[i][j])
                putchar('x');
            else if (out[i][j])
                putchar('o');
            else
                putchar('_');
        puts("");
    }
}