题面太鬼畜不粘了。
题意就是给一张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][1<<10],n,m,a[N][N],tot; bool tag[N][N]; const int dx[4]={-1,0,0,1}; const int dy[4]={0,-1,1,0}; struct node{ int x,y,s; }pre[N][N][1<<10]; 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=0;i<4;++i){ int vx=ux+dx[i],vy=uy+dy[i]; if(vx>0&&vy>0&&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]=1; 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=1;i<=n;++i) for(int j=1;j<=m;++j){ scanf("%d",&a[i][j]); if(!a[i][j])dp[i][j][1<<tot]=0,tot++; else dp[i][j][0]=a[i][j]; } int ma=(1<<tot)-1; for(int s=0;s<=ma;++s){ for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ for(int S=s;S;S=s&(S-1)) 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=1;i<=n;++i)for(int j=1;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=1;i<=n;++i){ for(int j=1;j<=m;++j){ if(!a[i][j])printf("x"); else if(tag[i][j])printf("o"); else printf("_"); } puts(""); } return 0; }