题面太鬼畜不粘了。
题意就是给一张n*m的网格图，每个点有点权，有k个关键点，让你把这k个关键点连成一个联通快的最小代价。
题解
这题nmk都非常小，解法肯定是状压，比较一般的解法插头dp，但不太好写。
但其实这道题是裸的斯坦纳树模型。
斯坦纳树是最小生成树的变形，在一般情况下是NP问题，但在k规模较少时可以用状压dp求解。
我们可以设dp[i][j][s]表示以(i,j)为根，覆盖关键点集合为s时的最小代价。
对于这个状态内部的更新，我们可以对s枚举子集，相当于把联通块拆成两部分再合并起来，dp[i][j][s] <= dp[i][j][S]+dp[i][j][s^S]。其中S是子集。
对于这个状态对外的更新，我们可以对和根有连边的点转移，dp[i'][j'][s']=dp[i][j][s]+a[i][j]。其实令s=s‘也可以，反正到了s‘时也得更新。
这种dp方法的好处就是只保留了一个转移点，降掉了我们枚举转移点的复杂度。
代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#define mm make_pair
#define N 11
using namespace std;
queue<pair<int,int> >q;
int ans,dp[N][N][<<],n,m,a[N][N],tot;
bool tag[N][N];
const int dx[]={-,,,};
const int dy[]={,-,,};
struct node{
int x,y,s;
}pre[N][N][<<];
inline void spfa(int x,int y,int s){
q.push(mm(x,y));
while(!q.empty()){
int ux=q.front().first,uy=q.front().second;q.pop();
for(int i=;i<;++i){
int vx=ux+dx[i],vy=uy+dy[i];
if(vx>&&vy>&&vx<=n&&vy<=m);else continue;
if(dp[vx][vy][s]>dp[ux][uy][s]+a[vx][vy]){
dp[vx][vy][s]=dp[ux][uy][s]+a[vx][vy];
pre[vx][vy][s]=node{ux,uy,s};
q.push(mm(vx,vy));
}
}
}
}
inline void findans(int x,int y,int s){
tag[x][y]=;
if(!x||!y)return;
int i=pre[x][y][s].x,j=pre[x][y][s].y,S=pre[x][y][s].s;
if(i==x&&j==y)findans(i,j,S),findans(i,j,s^S);
else findans(i,j,S);
}
int main(){
memset(dp,0x3f,sizeof(dp));
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)
for(int j=;j<=m;++j){
scanf("%d",&a[i][j]);
if(!a[i][j])dp[i][j][<<tot]=,tot++;
else dp[i][j][]=a[i][j];
}
int ma=(<<tot)-;
for(int s=;s<=ma;++s){
for(int i=;i<=n;++i)
for(int j=;j<=m;++j){
for(int S=s;S;S=s&(S-))
if(dp[i][j][s]>dp[i][j][S]+dp[i][j][s^S]-a[i][j]){
dp[i][j][s]=dp[i][j][S]+dp[i][j][s^S]-a[i][j];
pre[i][j][s]=node{i,j,S};
}
spfa(i,j,s);
}
}
int ans=2e9,prx,pry;
for(int i=;i<=n;++i)for(int j=;j<=m;++j)
if(dp[i][j][ma]<ans){
ans=min(ans,dp[i][j][ma]);prx=i,pry=j;
}
findans(prx,pry,ma);
cout<<ans<<endl;
for(int i=;i<=n;++i){
for(int j=;j<=m;++j){
if(!a[i][j])printf("x");
else if(tag[i][j])printf("o");
else printf("_");
}
puts("");
}
return ;
}