bzoj2595:[Wc2008]游览计划(斯坦纳树/状压DP)

Author Avatar
Sakits 1月 17, 2019

题解

  诈尸了(大雾
  今天看了一下THUSC2017D1T1,想了好久只会个不知道有多少分的插头DP,看了题解才知道斯坦纳树这种东西…
  大概就是一类只能在指数时间内求解的最小生成树…
  把它当作一种很强的状压DP就好辣 > <
  那接下来直接当作状压DP题写题解了…
  设 fi,j,kf_{i, j, k} 表示点 (i,j)(i, j) 在此方案中被选中,且景点的可到达状态为 kk 的最小代价,那么显然每次可以合并两个方案或者扩展一个方案。
  只有合并两个方案时才改变景点可到达状态,而扩展一个方案时不改变。
  转移一:合并两个方案

fi,j,k=minstkfi,j,st+fi,j,kstmpi,jf_{i, j, k} = \min\limits_{st \subset k} f_{i, j, st} + f_{i, j, k \oplus st} - mp_{i,j}

  这个显然可以直接DP转移
  转移二:扩展一个方案(点 (i,j)(i, j)(x,y)(x, y) 相邻)

fi,j,k=minfx,y,z+mpi,jf_{i, j, k} = \min f_{x, y, z} + mp_{i, j}

  这个转移没什么方向,这类大概都是用最短路解决,因为是三角不等式,这里可以用SPFA
  沧海桑田,码风已经发生了巨大的变化(逃

代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 50, inf = 1e9 + 233;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
struct poi{int x, y;}h[maxn * maxn];
struct trans{int i, j, k;}pre[maxn][maxn][1 << 10];
int n, m, front, rear, cnt;
int mp[maxn][maxn], f[11][11][1 << 10];
bool v[11][11];

template <typename T>
inline void read(T &k)
{
    int f = 1; k = 0; char c = getchar();
    while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
    while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
    k *= f;
}

void dfs(int x, int y, int st)
{
    if (!st) return; 

    v[x][y] = 1;

    int i = pre[x][y][st].i, j = pre[x][y][st].j, k = pre[x][y][st].k;
    dfs(i, j, k);
    if (i == x && j == y) dfs(i, j, st ^ k);
}

inline void solve(int x, int y)
{
    printf("%d\n", f[x][y][(1 << cnt) - 1]);

    memset(v, 0, sizeof(v));
    dfs(x, y, (1 << cnt) - 1);

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            putchar(mp[i][j] ? (v[i][j] ? 'o' : '_') : 'x');

        puts("");
    }
}

inline void spfa(int st)
{
    while (front != rear)
    {
        poi now = h[++front];
        if (front == maxn * maxn) front = -1;
        for (int i = 0; i < 4; i++)
        {
            poi nxt = (poi) {now.x + dx[i], now.y + dy[i]};

            if (nxt.x < 1 || nxt.y < 1 || nxt.x > n || nxt.y > m) continue;

            int delta = f[now.x][now.y][st] + mp[nxt.x][nxt.y];

            // printf("now.x:%d now.y:%d nxt.x:%d nxt.y:%d st:%d delta:%d\n", now.x, now.y, nxt.x, nxt.y, st, delta);

            if (f[nxt.x][nxt.y][st] > delta)
            {
                f[nxt.x][nxt.y][st] = delta;
                pre[nxt.x][nxt.y][st] = (trans) {now.x, now.y, st};

                if (!v[nxt.x][nxt.y]) 
                {
                    h[++rear] = (poi) {nxt.x, nxt.y};
                    if (rear == maxn * maxn) rear = -1;

                    v[now.x][now.y] = 1;
                }
            }
        }

        v[now.x][now.y] = 0;
    }
}

int main()
{
    memset(f, 0x3f, sizeof(f));

    read(n); read(m); cnt = 0;
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= m; j++)
        {
            read(mp[i][j]); 
            if (!mp[i][j]) f[i][j][1 << cnt] = 0, cnt++;
        }
    }

    for (int i = 1; i < (1 << cnt); i++)
    {
        front = rear = 0;
        memset(v, 0, sizeof(v));

        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= m; k++)
            {
                for (int st = i; st; st = (st - 1) & i)
                {
                    int delta = f[j][k][st] + f[j][k][i ^ st] - mp[j][k];
                    if (f[j][k][i] > delta)
                    {
                        f[j][k][i] = delta;
                        pre[j][k][i] = (trans) {j, k, st};
                    }
                }

                // printf("j:%d k:%d i:%d f:%d\n", j, k, i, f[j][k][i]);
                if (f[j][k][i] < inf) h[++rear] = (poi) {j, k}, v[j][k] = 1;
            }
        }

        spfa(i);
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            if (!mp[i][j]) return solve(i, j), 0;
    }
}