题目大意：有n*m的方格，每个格子有一个非负权值v(i,j)，现要求选出若干个格子，使得权值为0的格子联通且选出格子的数字和尽量小。
SPFA算法的优化及应用中的P20，3.2在一类状态转移阶段性不明显的动态规划中的应用。
这里暂不介绍插头DP的做法。
#include <cstdio> #include <algorithm> #include <cstring> #include <queue> #define N 12 #define INF 1061109567 using namespace std; typedef pair<int,int> pii; const int xx[]={1,-1,0,0},yy[]={0,0,1,-1}; int n,m,k,f[N][N][1<<N],a[N][N],b[N][N]; queue<pii> q; bool inq[N*N],jud[N][N]; struct Info { int x,y,z; Info(int _x=0,int _y=0,int _z=0):x(_x),y(_y),z(_z){} }from[N][N][1<<N]; void SPFA(int now) { while(!q.empty()) { pii tmp=q.front(); q.pop(); int x=tmp.first,y=tmp.second,z=b[x][y]; inq[z]=false; for(int i=0;i<4;i++) { int nx=x+xx[i],ny=y+yy[i],nz=b[nx][ny]; if(nx<1 || nx>n || ny<1 || ny>m) continue; if(f[nx][ny][now]>f[x][y][now]+a[nx][ny]) { f[nx][ny][now]=f[x][y][now]+a[nx][ny]; if (!inq[nz]) q.push(pii(nx,ny)),inq[nz]=true; from[nx][ny][now]=Info(x,y,now); } } } return ; } void dfs(int x,int y,int now) { int fromx=from[x][y][now].x,fromy=from[x][y][now].y,fromz=from[x][y][now].z; if(!fromz) return; jud[x][y]=true; dfs(fromx,fromy,fromz); if(fromx==x && fromy==y) dfs(x,y,now^fromz); return ; } int main() { ///input scanf("%d%d",&n,&m); memset(f,0x3f,sizeof f); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&a[i][j]); b[i][j]=(i-1)*n+j; if(!a[i][j]) f[i][j][1<<(k++)]=0; } ///DP for(int now=1;now<(1<<k);now++) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { for(int s=now&(now-1);s;s=now&(s-1)) if(f[i][j][now]>f[i][j][s]+f[i][j][now-s]-a[i][j]) f[i][j][now]=f[i][j][s]+f[i][j][now-s]-a[i][j], from[i][j][now]=Info(i,j,s); if(f[i][j][now]!=INF) q.push(pii(i,j)), inq[b[i][j]]=true; } SPFA(now); } ///output int x,y; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!a[i][j]) {x=i, y=j; break;} printf("%d\n",f[x][y][(1<<k)-1]); dfs(x,y,(1<<k)-1); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(!a[i][j]) printf("x"); else if(jud[i][j]) printf("o"); else printf("_"); } printf("\n"); } return 0; }