Luogu

分析

斯坦纳树模板题。

设 $f_{i, S}$ 表示 $i$ 号结点，与其它节点连通性为 $S$ 时的最小代价。

转移分两种情况：

• 由子集转移而来
  $$
  f_{i, S} = \min_{T \subseteq S} \left\{ f_{i, T} + f_{i, S - T} - val_i \right\}
  $$

• 由不含该节点的状态转移而来
  $$
  f_{i, S} = \min_{(i, j) \in \mathbb{E}} \left\{ f_{j, S} + val_i \right\}
  $$

第二个方程是有后效性的，但是它长得很像三角形不等式，所以可以跑最短路转移。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10+1;
const int INF=0x3f3f3f3f;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n,m,tot=0;
int a[N][N];
int f[N][N][1<<10];
struct node { int x,y,S; } pre[N][N][1<<10];
struct Point { int x,y; } view[N];

queue<Point> Q;
int inq[N][N];
inline void SPFA(int S) {
    while (!Q.empty()) {
        Point u=Q.front(); Q.pop();
        int x=u.x,y=u.y; inq[x][y]=0;
        for (re int d=0;d<4;++d) {
            int X=x+dx[d],Y=y+dy[d];
            if (X<1||X>n||Y<1||Y>m) continue;
            if (f[x][y][S]+a[X][Y]<f[X][Y][S]) {
                f[X][Y][S]=f[x][y][S]+a[X][Y];
                pre[X][Y][S]=(node){x,y,S};
                if (!inq[X][Y]) inq[X][Y]=1,Q.push((Point){X,Y});
            }
        }
    }
}

int vis[N][N];
inline void dfs(int x,int y,int S) {
    vis[x][y]=1;
    node t=pre[x][y][S];
    if (!t.x&&!t.y) return;
    dfs(t.x,t.y,t.S);
    if (t.x==x&&t.y==y) dfs(t.x,t.y,S-t.S);
}

int main() {
    n=read(),m=read();
    memset(f,0x3f,sizeof(f));
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j) {
            a[i][j]=read();
            if (!a[i][j])
                f[i][j][1<<tot]=0,view[tot]=(Point){i,j},++tot;
        }
    for (re int S=0;S<(1<<tot);++S) {
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=m;++j) {
                for (re int sub=S;sub;sub=(sub-1)&S) {
                    if (f[i][j][sub]+f[i][j][S-sub]-a[i][j]<f[i][j][S]) {
                        f[i][j][S]=f[i][j][sub]+f[i][j][S-sub]-a[i][j];
                        pre[i][j][S]=(node){i,j,sub};
                    }
                }
                Q.push((Point){i,j}),inq[i][j]=1;
            }
        SPFA(S);
    }
    dfs(view[0].x,view[0].y,(1<<tot)-1);
    printf("%d\n",f[view[0].x][view[0].y][(1<<tot)-1]);
    for (re int i=1;i<=n;++i) {
        for (re int j=1;j<=m;++j) {
            if (!a[i][j]) putchar('x');
            else if (vis[i][j]) putchar('o');
            else putchar('_');
        }
        putchar('\n');
    }
    return 0;
}