[WC2008]游覽計劃（斯坦納樹）

[Luogu4294]

題解 : 斯坦納樹

\(dp[i][j]\) 表示以\(i\)號節點為根，當前狀態為\(j\)（與\(i\)連通的點為\(1\)）

當根\(i\)不改變時狀態轉移方程是：

\(dp[i][j] = \min_{s \in j}\{dp[i][s] + dp[i][\complement_js] - val[i]\}\)

當根改變時,要求\(i,k\)相鄰 :

\(dp[i][j] = \min\{dp[k][j] + val[i]\}\)

記錄\(pre[i][now]\)為由哪個狀態轉移而來,便于輸出方案

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int INF=1e9+7;
inline LL read(){register LL x=0,f=1;register char c=getchar();while(c<48||c>57){if(c=='-')f=-1;c=getchar();}while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();return f*x;
}int f[101][1111],a[101],d[4][2]={1,0,0,1,0,-1,-1,0};
bool inq[101],ans[11][11];
pii pre[101][1111];
queue <int> q;
int n,m,K,rt;inline void SPFA(int now){while(!q.empty()){int u=q.front();q.pop();inq[u]=0;for(int i=0;i<4;i++){int x=u/m,y=u%m,tx=x+d[i][0],ty=y+d[i][1],v=tx*m+ty;if(tx<0||tx>=n||ty<0||ty>=m) continue;if(f[u][now]+a[v]<f[v][now]){f[v][now]=f[u][now]+a[v];if(!inq[v]) inq[v]=1,q.push(v);pre[v][now]=pii(u,now);//狀態為now定義為與根相連的點的狀態,只有相鄰的才能轉移}}}
}inline void dfs(int x,int y,int now){int u=x*m+y;if(!pre[u][now].second) return;ans[x][y]=1;if(pre[u][now].first==u) dfs(x,y,now^pre[u][now].second);//如果是由自己更新過來,就要往兩個方向回溯dfs(pre[u][now].first/m,pre[u][now].first%m,pre[u][now].second);//否則就只往一個方向
}int main(){n=read(),m=read();memset(f,0x3f,sizeof f);for(int i=0,now=0;i<n;i++)for(int j=0;j<m;j++,now++){a[now]=read();if(!a[now]) f[now][1<<(K++)]=0,rt=now;}for(int now=1;now<(1<<K);now++){for(int i=0;i<n*m;i++){for(int s=now&(now-1);s;s=(s-1)&now)if(f[i][s]+f[i][now^s]-a[i]<f[i][now]){f[i][now]=f[i][s]+f[i][now^s]-a[i];//用自己的信息更新pre[i][now]=pii(i,s);}if(f[i][now]<f[0][0])q.push(i),inq[i]=1;}SPFA(now);//更新狀態為now的全部的值}printf("%d\n",f[rt][(1<<K)-1]);dfs(rt/m,rt%m,(1<<K)-1);for(int i=0,now=0;i<n;i++){for(int j=0;j<m;j++,now++){if(!a[now]) putchar('x');else putchar(ans[i][j]?'o':'_');}putchar('\n');}
}