最小斯坦纳树用于处理联通集合中指定的点的最小代价，一般来说可以通过其他不属于集合的点
最小生成树是特殊的斯坦纳树，它适用于联通集合中的所有点。
对于斯坦纳树，从两方面考虑他，首先我们定义f[i][s]表示以i为根，联通状态为s的情况
对于更新，从两个方面考虑，第一个方面，根不变，枚举子集更新当前状态
第二个方面，子集不变，通过旁边的点来更新当前根
这两个的顺序不能改变，因为我们要保证在第二种情况更新的时候，当前联通所处的状态已经是最小值
对于为什么第二步更新必须存在但是只需要更新当前的状态呢。
有一个合理的解释是，因为更加后面的状态一定会从下一次的第一步来枚举更新出来。但是更新完后，当前状态并不一定是最小值
因为可能在真实的图上是有路径重叠的，因此我们可以通过其他额外的不在集合中的点来更新他。
对于第一步，使用状压dp，对于第二步，使用spfa来更新，因为第二步是一个三角不等式，可以进行松弛操作.
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; typedef pair<int,pll> plll; const int N=1e6+10; const int inf=0x3f3f3f3f; const int mod=1e9+7; int a[20][20]; int f[20][20][1050]; int st[20][20]; struct node{ int a,b; int now; }pre[20][20][1050]; queue<node> q; int n,m; int dx[]={-1,0,1,0}; int dy[]={0,1,0,-1}; void spfa(int state){ while(q.size()){ auto t=q.front(); q.pop(); st[t.a][t.b]=0; int i; for(i=0;i<4;i++){ int x=t.a+dx[i]; int y=t.b+dy[i]; if(x&&x<=n&&y&&y<=m){ if(f[x][y][state]>f[t.a][t.b][state]+a[x][y]){ f[x][y][state]=f[t.a][t.b][state]+a[x][y]; pre[x][y][state]={t.a,t.b,state}; if(!st[x][y]){ q.push({x,y,state}); st[x][y]=1; } } } } } } void dfs(int a,int b,int state){ if(!a||!b) return ; st[a][b]=1; auto x=pre[a][b][state]; dfs(x.a,x.b,x.now); if(x.a==a&&x.b==b) dfs(x.a,x.b,state-x.now); //因为是从补集转移，因此另一边的补集也要查询 } int main(){ ios::sync_with_stdio(false); cin>>n>>m; int i,j; int num=0; memset(f,0x3f,sizeof f); for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ cin>>a[i][j]; if(!a[i][j]){ f[i][j][1<<num]=0; num++; } } } int all=(1<<num)-1; for(int state=0;state<1<<num;state++){ for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ for(int s=state;s;s=(s-1)&state){ if(f[i][j][state]>f[i][j][s]+f[i][j][state-s]-a[i][j]){ f[i][j][state]=f[i][j][s]+f[i][j][state-s]-a[i][j]; pre[i][j][state]={i,j,s}; } } if(f[i][j][state]<inf){ st[i][j]=1; q.push({i,j,state}); } } } spfa(state); } int ans=0x3f3f3f3f; int be=0,ed=0; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(f[i][j][all]<ans){ ans=f[i][j][all]; be=i,ed=j; } } } memset(st,0,sizeof st); dfs(be,ed,all); cout<<ans<<endl; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(!a[i][j]) cout<<"x"; else{ if(st[i][j]) cout<<"o"; else cout<<"_"; } } cout<<endl; } return 0; }
原文：https://www.cnblogs.com/ctyakwf/p/13556647.html
