洛谷P4294 [WC2008]游览计划题解

题目链接：P4294 [WC2008]游览计划

题意：

从未来过绍兴的 cxy 有幸参加了 Winter Camp 2008 ，他被这座历史名城的秀丽风景所吸引，强烈要求游览绍兴及其周边的所有景点。

主办者将绍兴划分为 $n$ 行 $m$ 列共 $n \times m$ 个方块，如下图 $(8\times 8)$：

景点含于方块内（图中的灰色部分），且一个方块至多有一个景点。无景点的方块视为路。

为了保证安全与便利，主办方依据路况和治安状况，在非景点的一些方块内安排不同数量的志愿者；在景点内聘请导游（导游不是志愿者）。在选择旅游方案时，保证任意两个景点之间，存在一条路径，在这条路径所经过的每一个方块都有志愿者或者该方块为景点。既能满足选手们游览的需要，又能够让志愿者的总数最少。

例如，在上面的例子中，在每个没有景点的方块中填入一个数字，表示控制该方块最少需要的志愿者数目：

图中用红色标出的方块区域就是一种可行的志愿者安排方案，一共需要 $20$ 名志愿者。

由图可见，两个相邻的景点是直接（有景点内的路）连通的（左下角的两个）。

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

输入格式：

第一行有两个整数， $n$ 和 $m$ ，描述方块的数目。

接下来 $n$ 行，每行有 $m$ 个非负整数，如果该整数为 $0$ ，则该方块为一个景点；

否则表示控制该方块至少需要的志愿者数目。相邻的整数用（若干个）空格隔开，

行首行末也可能有多余的空格。

输出格式：

由 $n+1$ 行组成。第一行为一个整数，表示你所给出的方案中安排的志愿者总数目。

接下来 $n$ 行，每行 $m$ 个字符，描述方案中相应方块的情况：

_（下划线）表示该方块没有安排志愿者；

o（小写英文字母o）表示该方块安排了志愿者；

x（小写英文字母x）表示该方块是一个景点；

数据范围：

$0 \le n ,m,k \le 10,~0\le a_i \le 2^{16}$ 。

经典的斯坦纳树。最小斯坦纳树的解法详见斯坦纳树学习笔记

这一题要输出方案，稍微麻烦一些。

具体做法是在每次成功更新 dp 答案时记录它是哪个状态转移来的

时间复杂度 $\mathcal{O}(nm3^k + n^2m2^k)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
typedef pair<int,pii> p3i;
#define DDD cout << "line here is" << __LINE__ << '\n'
#define Fi first
#define Se second
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(12))
#define M ((int)(12))
#define L ((int)((1 << 10) + 15))

int n,m,k,o,tot,a[N*M + 5],ans[N][M],f[L][N*M + 5];
queue<pii> q; bitset<N*M + 5> vis; char buf[2*N*M]; p3i g[L][N*M+5];
const int dx[5] = {1,-1,0,0};
const int dy[5] = {0,0,1,-1};
#define ID(x,y) ((x) * m + (y))
bool safe(int x,int y) { return x >= 0 && y >= 0 && x < n && y < m; }
void spfa(int S)
{
    int *d = f[S]; p3i *r = g[S]; while(!q.empty()) q.pop();
    for(int i=0; i<tot; i++)
        if(d[i] != INF) q.push({i / m, i % m}), vis[i] = 1;
    for(int u,v,tx,ty; !q.empty(); )
    {
        pii tmp = q.front(); q.pop();
        vis[u = ID(tmp.Fi,tmp.Se)] = 0;
        for(int i=0; i<4; i++)
        {
            tx = tmp.Fi + dx[i]; ty = tmp.Se + dy[i];
            if(!safe(tx,ty)) continue; v = ID(tx,ty);
            if(d[v] > d[u] + a[v])
            {
                d[v] = d[u] + a[v]; r[v] = {S,tmp};
                if(!vis[v]) { vis[v] = 1; q.push({tx,ty}); }
            }
        }
    }
}
void dfs(int S,pii now)
{
    int u = ID(now.Fi, now.Se); p3i whi = g[S][u];
    if(!whi.Fi) return;
    ans[now.Fi][now.Se] = 1;
    if(whi.Se == now) dfs(S ^ whi.Fi, now);
    dfs(whi.Fi, whi.Se);
}
void solve()
{
    for(int i=0,id; i<n; buf[o++]='\n',i++) for(int j=0; j<m; j++)
    {
        if(!a[id = ID(i,j)]) buf[o++] = 'x';
        else buf[o++] = (ans[i][j] ? 'o' : '_');
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; tot = n * m; memset(f,0x3f,sizeof(f));
    for(int i=0,id; i<n; i++) for(int j=0; j<m; j++)
    {
        cin >> a[id = ID(i,j)];
        if(!a[id]) f[1 << k][id] = 0, ++k;
    }
    // cout << k << '\n';
    int mx = (1 << k) - 1;
    for(int S=1; S<=mx; spfa(S++))
        for(int T = S&(S-1); T; T = (T-1) & S)
            for(int i=0; i<tot; i++)
                if(f[S][i] > f[T][i] + f[S ^ T][i] - a[i])
                {
                    f[S][i] = f[T][i] + f[S ^ T][i] - a[i];
                    g[S][i] = {T, pii(i / m, i % m)};
                }
    int p = min_element(f[mx], f[mx]+tot) - f[mx];
    cout <<  f[mx][p]  << '\n';
    dfs(mx, {p / m, p % m}); solve(); cout << buf;
    return 0;
}