枚举子树的形态：dp[i][j]=min(dp[i][j]，dp[i][k]+dp[i][l])dp[i][j]=min(dp[i][j]，dp[i][k]+dp[i][l])，其中kk和ll是对j的一个划分 按照边进行松弛：dp[i][j]=min(dp[i][j]，dp[i′][j]+w[i][i′])dp[i][j]=min(dp[i][j]，dp[i′][j]+w[i][i′])，其中ii和i′i′之间有边相连
#include<bits/stdc++.h> using namespace std; struct precursor{int x,y,s;precursor(int a=0,int b=0,int c=0):x(a),y(b),s(c){}}pre[10][10][1025]; int n,m,K,f[10][10][1025],a[10][10]; bool vis[10][10]; typedef pair<int,int>par; queue<pair<int,int> >q; inline void read(int &x){ char ch=getchar();x=0;int f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} x*=f; } const int inf=2139062143,x[]={1,0,-1,0},y[]={0,1,0,-1}; inline void spfa(int sta){ while(!q.empty()){ par u=q.front();q.pop();vis[u.first][u.second]=0; for(int i=0;i<4;i++){ int fx=u.first+x[i],fy=u.second+y[i]; if(fx<0 || fx>=n || fy<0 || fy>=m)continue; if(f[fx][fy][sta]>f[u.first][u.second][sta]+a[fx][fy]){ f[fx][fy][sta]=f[u.first][u.second][sta]+a[fx][fy]; pre[fx][fy][sta]=precursor(u.first,u.second,sta); if(!vis[fx][fy])q.push(make_pair(fx,fy)),vis[fx][fy]=1; } } } } inline void dfs(int x,int y,int sta){ if(pre[x][y][sta].s==0)return;vis[x][y]=1; precursor nex=pre[x][y][sta]; dfs(nex.x,nex.y,nex.s); if(nex.x==x && nex.y==y)dfs(x,y,sta-nex.s); } int main(){ read(n),read(m); memset(f,127,sizeof f); for(int i=0;i<n;i++)for(int j=0;j<m;j++){read(a[i][j]);if(!a[i][j])f[i][j][1<<(K++)]=0;} for(int sta=1;sta<(1<<K);sta++){ for(int i=0;i<n;i++)for(int j=0;j<m;j++){ for(int s=sta&(sta-1);s;s=(s-1)&sta) if(f[i][j][sta]>f[i][j][s]+f[i][j][sta-s]-a[i][j]){ f[i][j][sta]=f[i][j][s]+f[i][j][sta-s]-a[i][j]; pre[i][j][sta]=precursor(i,j,s); } if(f[i][j][sta]!=inf)q.push(make_pair(i,j)),vis[i][j]=1; } spfa(sta); } int fx=0,fy=0; for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(!a[i][j])fx=i,fy=j; printf("%d\n",f[fx][fy][(1<<K)-1]); dfs(fx,fy,(1<<K)-1); for(int i=0;i<n;i++){ for(int j=0;j<m;j++) if(!a[i][j])putchar('x');else if(vis[i][j])putchar('o');else putchar('_'); puts(""); } return 0; }转载于:https://www.cnblogs.com/MikuKnight/p/9406639.html
相关资源：JAVA上百实例源码以及开源项目