题目概述

在 $n\times m$ 的网格上有 $k$ 个景点，选取每个网格都有代价，求最小代价使得景点之间全部连通。

解题报告

感觉这个东西好mogical啊……定义 $f_{i,j,s}$ 表示当 $i,j$ 与 $s$ 这些景点连通时的最优解，那么有两种方法转移：

• 通过子集转移：$f_{i,j,t}+f_{i,j,s-t}-cost_{i,j}\to f_{i,j,s}$ ，减去 $cost_{i,j}$ 是因为算重复了。
• 通过相邻点转移：$f_{x,y,s}+cost_{i,j}\to f_{i,j,s}$ 。

但是这个DP后效性已经飞天了，由于第二种转移和最短路长得很像，所以考虑用Spfa（没错就是SpfaQAQ）进行，每次先用第一种转移处理出 $f_{i,j,s}$ ，然后把 $f_{i,j,s}$ 加进队列，对每个 $s$ 都做一遍Spfa。

复杂度……可能是 $O(n^23^n+n^22^n)=O(n^23^n)$ ？至于为什么叫这个名字，我怎么知道。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10,maxk=10,maxs=1<<maxk,maxt=maxn*maxn;
const int dif[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int n,m,K,pic[maxn+5][maxn+5],f[maxn+5][maxn+5][maxs];
struct data {int i,j,s;} fa[maxn+5][maxn+5][maxs],que[maxt+5];
int INF,Head,Tail;bool vis[maxn+5][maxn+5];

inline bool Fix(int &x,int y) {if (y<x) return x=y,true;return false;}
#define AM(x) ((x)<maxt?(x)+1:0)
inline void Spfa(int s){
    while (Head!=Tail){
        data now=que[Head=AM(Head)];int x=now.i,y=now.j;vis[x][y]=false;
        for (int t=0;t<4;t++){
            int xx=x+dif[t][0],yy=y+dif[t][1];if (xx<1||xx>n||yy<1||yy>m) continue;
            if (Fix(f[xx][yy][s],f[x][y][s]+pic[xx][yy])){
                fa[xx][yy][s]=(data){x,y,s};if (vis[xx][yy]) continue;
                que[Tail=AM(Tail)]=(data){xx,yy,s};vis[xx][yy]=true;
            }
        }
    }
}
void Path(int x,int y,int s){
    if (!x&&!y) return;data now=fa[x][y][s];int i=now.i,j=now.j,t=now.s;
    vis[x][y]=true;Path(i,j,t);if (x==i&&y==j) Path(i,j,s^t);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);memset(f,63,sizeof(f));INF=f[0][0][0];int X,Y;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            scanf("%d",&pic[i][j]),pic[i][j]?0:f[X=i][Y=j][1<<K++]=0;
    for (int s=1;s<(1<<K);Spfa(s),s++,Head=Tail=0){
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++){
                for (int t=(s-1)&s;t;t=(t-1)&s)
                    if (Fix(f[i][j][s],f[i][j][t]+f[i][j][s^t]-pic[i][j]))
                        fa[i][j][s]=(data){i,j,t};
                if (f[i][j][s]<INF) que[Tail=AM(Tail)]=(data){i,j,s},vis[i][j]=true;
            }
    }printf("%d\n",f[X][Y][(1<<K)-1]);Path(X,Y,(1<<K)-1);
    for (int i=1;i<=n;i++,puts(""))
        for (int j=1;j<=m;j++) putchar(!pic[i][j]?'x':(vis[i][j]?'o':'_'));return 0;
}