题目大意：
选定一些格子保证景点对应的格子通过这些格子连通，保证选定的所有格子对应的权值和最小
这是相当于理解为将所有点形成的最小生成树
这里点的个数很少，所以可以对每一个点进行状态压缩
f[st][i]表示连通性至少为st，且经过i点的最小距离
方程1.f[st][i] = Min{f[s][i] + f[st - s][i]}(s为st的子集)
方程2.f[st][i] = Min{f[st][j] + w(i,j)}(i,j之间有边相连)
那么可以看出来大的状态总是跟小的状态有关，那么总是先求出小的状态集合
利用spfa求解所有状态对应的点跑最短路对其他格点进行松弛
我到现在也不知道为什么这样写效率会高
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int,int> pii;
#define N 11
const int MAXN=<<N;
const int INF = 0x3f3f3f3f;
int n , m ; struct Node{
int x , y , s;
Node(){}
Node(int x , int y , int s):x(x),y(y),s(s){}
};
Node pre[N][N][MAXN];//用于回溯找上一个节点 int w[N][N] , dp[N][N][MAXN] , dir[][]={{,},{,-},{,},{-,}};
bool vis[N][N] , flag[N][N];
queue<pii> que; bool ok(int x , int y){return x>=&&x<=n&&y>=&&y<=m;} void spfa(int state)
{
while(!que.empty()){
pii u = que.front();
que.pop();
int x = u.first , y = u.second;
vis[x][y] = false;
for(int i= ; i< ; i++){
int xx = x+dir[i][] , yy = y+dir[i][];
if(!ok(xx,yy)) continue;
if(dp[xx][yy][state]>dp[x][y][state]+w[xx][yy]){
dp[xx][yy][state]=dp[x][y][state]+w[xx][yy];
pre[xx][yy][state] = Node(x , y , state);
if(!vis[xx][yy]) que.push(make_pair(xx , yy));
}
}
}
} void huisu(int x , int y , int s)
{
flag[x][y] = true;
if(pre[x][y][s].s == ) return;
huisu(pre[x][y][s].x , pre[x][y][s].y , pre[x][y][s].s);
if(pre[x][y][s].x==x && pre[x][y][s].y==y) huisu(pre[x][y][s].x , pre[x][y][s].y , s-pre[x][y][s].s);
} void print()
{
for(int i= ; i<=n ; i++){
for(int j= ; j<=m ; j++)
if(!w[i][j]) printf("x");
else if(flag[i][j]) printf("o");
else printf("_");
puts("");
}
} int main()
{
// freopen("in.txt" , "r" , stdin);
while(~scanf("%d%d" , &n , &m))
{
int num = ;
memset(dp , 0x3f , sizeof(dp));
memset(pre , , sizeof(pre));
for(int i= ; i<=n ; i++){
for(int j= ; j<=m ; j++){
scanf("%d" , &w[i][j]);
if(!w[i][j]){
dp[i][j][<<num] = ;
num++;
}
}
}
int ALL_STATE = <<num;
for(int k= ; k<ALL_STATE ; k++){
for(int i= ; i<=n ; i++){
for(int j= ; j<=m ; j++){
for(int s=(k-)&k ; s ; s=(s-)&k){
int tmps = k-s;
if(dp[i][j][k]>dp[i][j][s]+dp[i][j][tmps]-w[i][j]){
dp[i][j][k] = dp[i][j][s]+dp[i][j][tmps]-w[i][j];
pre[i][j][k] = Node(i , j , s);
}
}
if(dp[i][j][k]<INF) que.push(make_pair(i , j)) , vis[i][j]=true;
}
}
spfa(k);
}
memset(flag , , sizeof(flag));
for(int i= ; i<=n ; i++)
for(int j= ; j<=m ; j++){
if(!w[i][j]){
cout<<dp[i][j][ALL_STATE-]<<endl;
huisu(i , j , ALL_STATE-);
print();
return ;
}
} }
return ;
}