斯坦纳树
f[i][zt]表示以i为根，连成的联通块包括那些景点
两个转移：f[i][zt]=f[i][tzt]+f[i][zt^tzt]-a[i]
f[i][zt]=f[j][zt]+a[i] ((i,j)相邻)
后面这个可以用spfa优化
记得先进行前一个转移，还有容斥减掉a[i]
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define P(x,y) m*(x-1)+y using namespace std; const int dx[4]={-1,0,1,0}; const int dy[4]={0,1,0,-1}; int c[110]; int cnt,f[110][2100],fr[110][2100]; struct node { int x,y,next; }a[410];int len,last[110]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } int head,tail,list[110]; bool v[110]; void add(int &x){x++;if(x==105)x=1;} void spfa(int zt) { while(head!=tail) { int x=list[head]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(f[y][zt]>f[x][zt]+c[y]) { f[y][zt]=f[x][zt]+c[y]; fr[y][zt]=-x; if(v[y]==false) { v[y]=true; list[tail]=y; add(tail); } } } v[x]=false; add(head); } } char ss[110]; void dfs(int x,int zt) { if(ss[x]!='x')ss[x]='o'; if(fr[x][zt]>0) dfs(x,fr[x][zt]),dfs(x,zt^fr[x][zt]); else if(fr[x][zt]<0) dfs(-fr[x][zt],zt); } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int n,m; scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); memset(f,63,sizeof(f)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&c[P(i,j)]); if(c[P(i,j)]==0)cnt++,f[P(i,j)][1<<(cnt-1)]=0; for(int k=0;k<=3;k++) { int x=dx[k]+i,y=dy[k]+j; if(1<=x&&x<=n&&1<=y&&y<=m) ins(P(i,j),P(x,y)); } } //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~init~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int li=(1<<cnt)-1; head=1,tail=1; for(int zt=1;zt<=li;zt++) { for(int i=1;i<=n*m;i++) for(int tzt=((zt-1)&zt);tzt!=0;tzt=((tzt-1)&zt)) if(f[i][zt]>f[i][tzt]+f[i][zt^tzt]-c[i]) { f[i][zt]=min(f[i][zt],f[i][tzt]+f[i][zt^tzt]-c[i]); fr[i][zt]=tzt; } memset(v,false,sizeof(v)); for(int i=1;i<=n*m;i++) if(f[i][zt]!=f[0][0]) { v[i]=true; list[tail]=i,add(tail); } spfa(zt); } //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~DP~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int mmin=f[0][0],id; for(int i=1;i<=n*m;i++) if(f[i][li]<mmin)mmin=f[i][li],id=i; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(c[P(i,j)]==0)ss[P(i,j)]='x'; else ss[P(i,j)]='_'; dfs(id,li); printf("%d\n",mmin); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) printf("%c",ss[P(i,j)]); printf("\n"); } //~~~~~~~~~~~~~~~~~~~~~~~~~print~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ return 0; }